二叉树的各种遍历姿势

爱被打了一巴掌 2023-02-09 14:11 1阅读 0赞

# 前言 #

## Node节点 ##

public static class TreeNode { 
        TreeNode left;
        TreeNode right;
        int val;
    }

## 定义 ##

*  先序遍历：先访问根，再访问左子树，最后访问右子树
 *  中序遍历：先访问左子树，再访问根，最后访问右子树
 *  后序遍历：先访问左子树，再访问右子树，最后访问根

# 递归式模板 #

public static List<Integer> view(TreeNode root, List<Integer> result) { 
        if(null == root) { 
            return result;
        }
        result.add(root.val);     // 根
        view(root.left, result);  // 左
        // result.add(root.val);
        view(root.right, result); // 右
        // result.add(root.val);
        return result;
    }

> 由根的访问时机可以得到不同的遍历顺序，根左右为先序，左根右为中序，左右根为后序

# 非递归式模板 #

## 先序、中序 ##

public static List<Integer> preInOrder(TreeNode root) { 
        List<Integer> result = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while (null != cur || !stack.isEmpty()) { 
            if (null != cur) { 
                stack.push(cur);     // 入栈
                result.add(cur.val); // 访问（先序）
                cur = cur.left;      // 左行
            } else { 
                cur = stack.pop();   // 出栈
                // result.add(cur.val); // 访问（中序）
                cur = cur.right;     // 右行
            }
        }
    
        return result;
    }

> 入栈和左行之间访问节点，得到的是先序  
> 出栈和右行之间访问节点，得到的是中序

## 后序 ##

public static List<Integer> postOrder(TreeNode root) { 
        List<Integer> result = new ArrayList<>();
        Stack<TreeNode> tmp = new Stack<>();     // 辅助栈
        Stack<TreeNode> stack = new Stack<>();   // 主栈
        
        tmp.push(root);
        TreeNode cur = null;
        while (!tmp.isEmpty()) { 
            // 从辅助栈取一个节点
            cur = tmp.pop();
    
    		// 依次将其左右节点入辅助栈
            if (null != cur.left) { 
                tmp.push(cur.left);
            }
            if (null != cur.right) { 
                tmp.push(cur.right);
            }
    
    		// 当前节点入主栈
            stack.push(cur);
        }
        
        while (!stack.isEmpty()) { 
            result.add(stack.pop().val);
        }
    
        return result;
    }

> 从辅助栈取出一个节点，**依次将其左节点–>右节点压入辅助栈，再将本身压入主栈**，循环至辅助栈空。  
> 最后从主栈取出，根据栈性质易知得到的是**左–>右–>根**的顺序，即为后序。

## 层序 ##

public static List<Integer> levelOrder(TreeNode root) { 
    	Queue<Integer> queue = new LinkList<Integer>();
    	List<Integer> result = new ArrayList<>();
    	if(null == root || null == root.val){ 
    		return result;
    	}
    	
    	queue.add(root.val);
    	while(!queue.isEmpty()) { 
    		Integer e = queue.poll();
    		result.add(e);
    
    		// 左右节点入队列
    		if(null != e.left) { 
    			queue.offer(e.left);
    		}
    		if(null != e.right) { 
    			queue.offer(e.right);
    		}
    	}
    	
    	return result;
    }