Leetcode 二叉树四种遍历方式总结

客官°小女子只卖身不卖艺 2021-10-12 19:58 244阅读 0赞

### 文章目录 ###

*  1. 前序遍历
 *  2. 中序遍历
 *  3. 后序遍历
 *  4. 层序遍历

# 1. 前序遍历 #

[Leetcode 144. 二叉树的前序遍历][Leetcode 144.]

**递归实现**：

class Solution { 
        public List<Integer> preorderTraversal(TreeNode root) { 
            List<Integer> res = new ArrayList<>();
            helper(root, res);
            return res;
        }
    
        private void helper(TreeNode root, List<Integer> res) { 
            if (root == null) { 
                return;
            }
    
            res.add(root.val);
            helper(root.left, res);
            helper(root.right, res);
        }
    }

**迭代实现**：沿左侧分支展开，同时压栈，直到左子树为空；弹出栈顶元素，转向右子树，重复上述步骤，直到栈为空。**该方法适用于三种遍历方式**。

1.  将当前节点压入栈中，节点值加入输出序列（前序遍历），跳转到左子树；
2.  重复过程 1，直到左子树为空；
3.  弹出栈顶元素，节点值加入输出序列（中序遍历），跳转到右子树；
4.  重复过程 1，直到栈为空。

class Solution { 
        public List<Integer> preorderTraversal(TreeNode root) { 
            if (root == null) { 
                return new ArrayList<>();
            }
    
            List<Integer> res = new ArrayList<>();
            Stack<TreeNode> stk = new Stack<>();
            while (true) { 
                while (root != null) { 
                    res.add(root.val);
                    stk.push(root);
                    root = root.left;
                }
                if (stk.isEmpty()) { 
                    break;
                }
                TreeNode node = stk.pop();
                root = node.right;
            }
            return res;
        }
    }

**迭代实现**：每次循环，右子节点先入后出，左子节点后入先出，利用栈的特性完成遍历，**仅适用于前序遍历**。

class Solution { 
        public List<Integer> preorderTraversal(TreeNode root) { 
            if (root == null) { 
                return new ArrayList<>();
            }
    
            List<Integer> res = new ArrayList<>();
            Stack<TreeNode> stk = new Stack<>();
            stk.push(root);
            while (!stk.isEmpty()) { 
                TreeNode node = stk.pop();
                res.add(node.val);
                if (node.right != null) { 
                    stk.push(node.right);
                }
                if (node.left != null) { 
                    stk.push(node.left);
                }
            }
            return res;
        }
    }

# 2. 中序遍历 #

[Leetcode 94. 二叉树的中序遍历][Leetcode 94.]

**递归实现**：

class Solution { 
        public List<Integer> inorderTraversal(TreeNode root) { 
            List<Integer> res = new ArrayList<>();
            helper(root, res);
            return res;
        }
    
        private void helper(TreeNode root, List<Integer> res) { 
            if (root == null) { 
                return;
            }
    
            helper(root.left, res);
            res.add(root.val);
            helper(root.right, res);
        }
    }

**迭代实现**：

class Solution { 
        public List<Integer> inorderTraversal(TreeNode root) { 
            if (root == null) { 
                return new ArrayList<>();
            }
    
            List<Integer> res = new ArrayList<>();
            Stack<TreeNode> stk = new Stack<>();
            while (true) { 
                while (root != null) { 
                    stk.push(root);
                    root = root.left;
                }
                if (stk.isEmpty()) { 
                    break;
                }
                TreeNode node = stk.pop();
                res.add(node.val);
                root = node.right;
            }
            return res;
        }
    }

# 3. 后序遍历 #

[Leetcode 145. 二叉树的后序遍历][Leetcode 145.]

**递归实现**：

class Solution { 
        public List<Integer> postorderTraversal(TreeNode root) { 
            List<Integer> res = new ArrayList<>();
            helper(root, res);
            return res;
        }
    
        private void helper(TreeNode root, List<Integer> res) { 
            if (root == null) { 
                return;
            }
    
            helper(root.left, res);
            helper(root.right, res);
            res.add(root.val);
        }
    }

**迭代实现**：后序遍历就是**逆前序遍历**的倒序输出，逆前序遍历即先访问根节点，再处理右子树，最后处理左子树。

*  前序遍历：根 -> 左 -> 右；
 *  逆前序遍历：根 -> 右 -> 左；
 *  后序遍历：左 -> 右 -> 根。

class Solution { 
        public List<Integer> postorderTraversal(TreeNode root) { 
            if (root == null) { 
                return new ArrayList<>();
            }
    
            List<Integer> res = new ArrayList<>();
            Stack<TreeNode> stk = new Stack<>();
            while (true) { 
                while (root != null) { 
                    res.add(root.val);
                    stk.push(root);
                    root = root.right;
                }
                if (stk.isEmpty()) { 
                    break;
                }
                TreeNode node = stk.pop();
                root = node.left;
            }
            Collections.reverse(res);
            return res;
        }
    }

**迭代实现**：后序遍历中，只有遍历完右子树，才能访问根节点。因此，需要引入变量记录上一次访问的节点，用于判断是否完成了对右子树的遍历。

class Solution { 
        public List<Integer> postorderTraversal(TreeNode root) { 
            if (root == null) { 
                return new ArrayList<>();
            }
    
            List<Integer> res = new ArrayList<>();
            Stack<TreeNode> stk = new Stack<>();
            TreeNode pre = null;
            while (root != null) { 
                pre = root;
                stk.push(root);
                root = root.left;
            }
            while (!stk.isEmpty()) { 
                TreeNode node = stk.peek();
                if (pre == node.right || node.right == null) { 
                    pre = stk.pop();
                    res.add(node.val);
                } else { 
                    root = node.right;
                    while (root != null) { 
                        pre = root;
                        stk.push(root);
                        root = root.left;
                    }
                }
            }
            return res;
        }
    }

# 4. 层序遍历 #

[Leetcode 102. 二叉树的层次遍历][Leetcode 102.]

**递归实现**：

class Solution { 
        public List<List<Integer>> levelOrder(TreeNode root) { 
            List<List<Integer>> res = new ArrayList<>();
            helper(root, 0, res);
            return res;
        }
    
        private void helper(TreeNode root, int level, List<List<Integer>> res) { 
            if(root == null) { 
                return;
            }
            if(level == res.size()) { 
                res.add(new ArrayList<>());
            }
            res.get(level).add(root.val);
            helper(root.left, level+1,res);
            helper(root.right,level+1,res);
        }
    }

**迭代实现**：

class Solution { 
        public List<List<Integer>> levelOrder(TreeNode root) { 
            if (root == null) { 
                return new ArrayList<>();
            }
    
            List<List<Integer>> res = new ArrayList<>();
            Queue<TreeNode> queue = new LinkedList<>();
            queue.add(root);
            while (!queue.isEmpty()) { 
                int n = queue.size();
                List<Integer> ans = new ArrayList<>();
                for (int i = 0; i < n; i++) { 
                    TreeNode node = queue.remove();
                    ans.add(node.val);
                    if (node.left != null) { 
                        queue.add(node.left);
                    }
                    if (node.right != null) { 
                        queue.add(node.right);
                    }
                }
                res.add(ans);
            }
            return res;
        }
    }

[Leetcode 144.]: https://leetcode-cn.com/problems/binary-tree-preorder-traversal/
[Leetcode 94.]: https://leetcode-cn.com/problems/binary-tree-inorder-traversal/
[Leetcode 145.]: https://leetcode-cn.com/problems/binary-tree-postorder-traversal/
[Leetcode 102.]: https://leetcode-cn.com/problems/binary-tree-level-order-traversal/