【LeetCode】二叉树的三种遍历方式前序中序后序递归方式迭代方式

叁歲伎倆 2021-06-10 20:37 476阅读 0赞

## 前言 ##

三种遍历方式对应着LeetCode的三道题目，分别是：  
前序遍历：[144. Binary Tree Preorder Traversal][]  
中序遍历：[94. Binary Tree Inorder Traversal][]  
后序遍历：[145. Binary Tree Postorder Traversal][]

先说一下，递归方式很简单，所以目前本文暂且都是递归方式，迭代方式还没添上，后续更新

三种遍历方式把，长得贼像，其实就是一个先添加哪个节点的问题

## 举例的二叉树 ##

![在这里插入图片描述][20200210173408546.png]  
总的来说把，除了空二叉树，这个树把树的每个节点的所有情况都包括了，拿来举例比较好  
前序遍历：A → B → D → E → G → C → F  
中序遍历：D → B → G → E → A → C → F  
后序遍历：D → G → E → B → F → C → A

## 树的数据结构 ##

这是自定义的一个TreeNode，很简单的结构，左节点、右节点、本身的值

class TreeNode { 
        int val;
        TreeNode left;
        TreeNode right;
    
        TreeNode(int x) { 
            val = x;
        }
    }

# 递归方式 #

## 前序遍历 ##

先遍历根节点，然后遍历它的左子树，再遍历它的右子树

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMTUxNTMxMjgzMg_size_16_color_FFFFFF_t_70]

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

## 中序遍历 ##

对于一个节点来说，先遍历左子树，再遍历本身，最后遍历右子树  
也就是要把一个树，拆成左子树、根节点、右子树这三部分  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMTUxNTMxMjgzMg_size_16_color_FFFFFF_t_70 1]

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

## 后序遍历 ##

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

# 迭代方式 #

[https://leetcode.com/problems/binary-tree-postorder-traversal/discuss/45551/Preorder-Inorder-and-Postorder-Iteratively-Summarization][https_leetcode.com_problems_binary-tree-postorder-traversal_discuss_45551_Preorder-Inorder-and-Postorder-Iteratively-Summarization]

注意链接是国际版leetcode，有可能会自动转向中国版leetcode

[144. Binary Tree Preorder Traversal]: https://leetcode-cn.com/problems/binary-tree-preorder-traversal/
[94. Binary Tree Inorder Traversal]: https://leetcode-cn.com/problems/binary-tree-inorder-traversal/
[145. Binary Tree Postorder Traversal]: https://leetcode-cn.com/problems/binary-tree-postorder-traversal/
[20200210173408546.png]: /images/20210529/bee8177c8080481d94e45fb49bbc4870.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMTUxNTMxMjgzMg_size_16_color_FFFFFF_t_70]: /images/20210529/38ac4159df1c4a488fc0173bee111e76.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMTUxNTMxMjgzMg_size_16_color_FFFFFF_t_70 1]: /images/20210529/fc84aeead94d482db1ff045b35edc0e2.png
[https_leetcode.com_problems_binary-tree-postorder-traversal_discuss_45551_Preorder-Inorder-and-Postorder-Iteratively-Summarization]: https://leetcode.com/problems/binary-tree-postorder-traversal/discuss/45551/Preorder-Inorder-and-Postorder-Iteratively-Summarization