二叉树的前、中、后序遍历和层序遍历的实现（递归 + 迭代）

女爷i 2023-09-28 23:17 1阅读 0赞

> 该篇文章写了二叉树的四种遍历方式，分别对应力扣上的题目为[144. 二叉树的前序遍历][144.]、[94. 二叉树的中序遍历][94.]、[145. 二叉树的后序遍历][145.]、[102. 二叉树的层序遍历][102.]。

##### 二叉树结点定义：  #####

public class TreeNode {
        
            int val;
            TreeNode left;
            TreeNode right;
    
            public TreeNode() {
        
            }
    
            public TreeNode(int val) {
        
                this.val = val;
            }
    
            public TreeNode(int val, TreeNode left, TreeNode right) {
        
                this.val = val;
                this.left = left;
                this.right = right;
            }
        }

##### 二叉树的递归遍历：  #####

前序遍历：

public void Preorder(List<Integer> list, TreeNode root) {
        
            if (root == null) {
        
                return;
            }
            //中-左-右
            list.add(root.val);
            Preorder(list, root.left);
            Preorder(list, root.right);
        }

中序遍历：

public void MesoOrder(List<Integer> list, TreeNode root) {
        
            if (root == null) {
        
                return;
            }
            //左-中-右
            MesoOrder(list, root.left);
            list.add(root.val);
            MesoOrder(list, root.right);
        }

后序遍历：

public void Postorder(List<Integer> list, TreeNode root) {
        
            if (root == null) {
        
                return;
            }
            //左-右-中
            Postorder(list, root.left);
            Postorder(list, root.right);
            list.add(root.val);
        }

层序遍历：

public void Sequence(List<List<Integer>> list, TreeNode root, int deep) {
        
            if (root == null) {
        
                return;
            }
            if (list.size() == deep) {
        
                list.add(new ArrayList<>());
            }
            list.get(deep).add(root.val);
            Sequence(list, root.left, deep + 1);
            Sequence(list, root.right, deep + 1);
        }

##### 二叉树的迭代遍历：  #####

前序遍历：

public List<Integer> preorderTraversal(TreeNode root) {
        
            List<Integer> res = new ArrayList<>();
            Deque<TreeNode> stack = new ArrayDeque<>();
            if (root != null) {
        
                stack.push(root);
            }
            while (!stack.isEmpty()) {
        
                TreeNode cur = stack.pop();
                res.add(cur.val);
                if (cur.right != null) {
        
                    stack.push(cur.right);
                }
                if (cur.left != null) {
        
                    stack.push(cur.left);
                }
            }
            return res;
        }

中序遍历：

public List<Integer> inorderTraversal(TreeNode root) {
        
            List<Integer> res = new ArrayList<>();
            Deque<TreeNode> stack = new ArrayDeque<>();
            TreeNode cur = root;
            while (cur != null || !stack.isEmpty()) {
        
                if (cur != null) {
        
                    stack.push(cur);
                    cur = cur.left;
                } else {
        
                    cur = stack.pop();
                    res.add(cur.val);
                    cur = cur.right;
                }
            }
            return res;
        }

后续遍历：

public List<Integer> postorderTraversal(TreeNode root) {
        
            List<Integer> res = new ArrayList<>();
            Deque<TreeNode> stack = new ArrayDeque<>();
            if (root != null) {
        
                stack.push(root);
            }
            while (!stack.isEmpty()) {
        
                TreeNode cur = stack.pop();
                res.add(cur.val);
                if (cur.left != null) {
        
                    stack.push(cur.left);
                }
                if (cur.right != null) {
        
                    stack.push(cur.right);
                }
            }
            Collections.reverse(res);
            return res;
        }

层序遍历：

public List<List<Integer>> levelOrder(TreeNode root) {
        
            List<List<Integer>> res = new ArrayList<>();
            Deque<TreeNode> stack = new ArrayDeque<>();
            if (root != null) {
        
                stack.offer(root);
            }
            while (!stack.isEmpty()) {
        
                int size = stack.size();
                List<Integer> list = new ArrayList<>();
                while (size-- != 0) {
        
                    TreeNode node = stack.poll();
                    list.add(node.val);
                    if (node.left != null) {
        
                        stack.offer(node.left);
                    }
                    if (node.right != null) {
        
                        stack.offer(node.right);
                    }
                }
                res.add(list);
            }
            return res;
        }

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