LeetCode-(94,144,145).二叉树的前中后续遍历

缺乏、安全感 2024-03-27 15:07 18阅读 0赞

#### 目录 ####

*   *  二叉树的前序遍历
     *  二叉树的中序遍历
     *  二叉树的后序遍历

### 二叉树的前序遍历 ###

**递归**  
![在这里插入图片描述][de774775564a48ce9272d1df82e6d0cf.png]

class Solution {
        
        public List<Integer> preorderTraversal(TreeNode root) {
        
            List<Integer> list = new ArrayList<>();
            dfs(root,list);
            return list;
        }
    
        public static void dfs(TreeNode root,List<Integer> list){
        
            if(root == null){
        
                return;
            }
            //中  左  右
            list.add(root.val);
            dfs(root.left,list);
            dfs(root.right,list);
        }
    }

![在这里插入图片描述][7b9603eed3fc4d6581755ce2f1e6ad94.png]  
**迭代**  
我们使用栈来进行迭代，过程如下：

*  初始化栈，并将根节点入栈；
 *  当栈不为空时：
    
     *  弹出栈顶元素 node，并将值添加到结果中；
     *  如果 node 的右子树非空，将右子树入栈；
     *  如果 node 的左子树非空，将左子树入栈；

由于栈是“先进后出”的顺序，所以入栈时先将右子树入栈，这样使得前序遍历结果为 “根->左->右”的顺序。  
![在这里插入图片描述][ace314f6071042e7b31535f419af9045.gif_pic_center]

// 前序遍历顺序：中-左-右，入栈顺序：中-右-左
    class Solution {
        
        public List<Integer> preorderTraversal(TreeNode root) {
        
            List<Integer> list = new ArrayList<>();
            if(root == null){
        
                return list;
            }
            Stack<TreeNode> stack = new Stack<>();
            stack.push(root);
            while(!stack.isEmpty()){
        
                TreeNode node = stack.pop();
                list.add(node.val);
                if(node.right != null){
        
                    stack.push(node.right);
                }
                if(node.left != null){
        
                    stack.push(node.left);
                }
            }
            return list;
        }
    }

![在这里插入图片描述][0d1a8451991f47a8813498855f00d595.png]

### 二叉树的中序遍历 ###

**递归**  
![在这里插入图片描述][650ba46d0f8947369c7961f363a1ccd0.png]

class Solution {
        
        public List<Integer> inorderTraversal(TreeNode root) {
        
            List<Integer> list = new ArrayList<>();
            dfs(root,list);
            return list;
        }
    
        public static void dfs(TreeNode root,List<Integer> list){
        
            if(root == null){
        
                return;
            }
            //左  中  右
            dfs(root.left,list);
            list.add(root.val);
            dfs(root.right,list);
        }
    }

![在这里插入图片描述][54d50e8daa4145db9156d1a99a59e81e.png]  
**迭代**  
会先递归节点A，再递归B，再递归D，一个个压入递归栈。  
![在这里插入图片描述][401ffcdb336c4a738bf094f3ce113040.png]  
中序遍历，在栈顶节点的右子节点压栈之前，要处理出栈节点的节点值，将它输出。  
![在这里插入图片描述][77578431d1cc4cf1af6632b499942339.png]  
新入栈的右子节点（右子树），就是在递归它。和节点A、B、D的压栈一样，它们都是子树。  
不同的子树要做同样的事情，一样要先将它的左子节点不断压栈，然后再出栈，带出右子节点入栈。  
![在这里插入图片描述][34d208abc1864079901b12daff27c48b.png]  
代码实现

// 中序遍历顺序: 左-中-右 入栈顺序： 左-右
    class Solution {
        
        public List<Integer> inorderTraversal(TreeNode root) {
        
            List<Integer> result = new ArrayList<>();
            if (root == null){
        
                return result;
            }
            Stack<TreeNode> stack = new Stack<>();
            TreeNode cur = root;
            while (cur != null || !stack.isEmpty()){
        
               if (cur != null){
        
                   stack.push(cur);
                   cur = cur.left;
               }else{
        
                   cur = stack.pop();
                   result.add(cur.val);
                   cur = cur.right;
               }
            }
            return result;
        }
    }

![在这里插入图片描述][b8b0d3d13b754bd2b1128fb40741b6fb.png]

### 二叉树的后序遍历 ###

**递归**

class Solution {
        
        public List<Integer> postorderTraversal(TreeNode root) {
        
            List<Integer> list = new ArrayList<>();
            dfs(root,list);
            return list;
        }
    
        public static void dfs(TreeNode root,List<Integer> list){
        
            if(root == null){
        
                return;
            }
            //左  右   中
            dfs(root.left,list);
            dfs(root.right,list);
            list.add(root.val);
        }
    }

![在这里插入图片描述][f048b61b8bfa41ee98933353adf18be2.png]

**迭代**  
根据前序遍历改  
前序遍历中左右—>中右左—>左右中(翻转)

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

![在这里插入图片描述][a1739f6c8ced4ae794a7da990e3bcfb8.png]

[de774775564a48ce9272d1df82e6d0cf.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/dd8bdfa40ec149fb937ebb94b17b6ce9.png
[7b9603eed3fc4d6581755ce2f1e6ad94.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/f5a40d57dd06450e9ac6ba70b7ecd188.png
[ace314f6071042e7b31535f419af9045.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/c2302ce7a21547a58b4318628ff24b64.png
[0d1a8451991f47a8813498855f00d595.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/525a45c3175c44529d06f36e705455d6.png
[650ba46d0f8947369c7961f363a1ccd0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/bd975dda9ed24d03a55315403f0101fd.png
[54d50e8daa4145db9156d1a99a59e81e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/e4a1ee6a2ac444a087d73ecad5a22c5e.png
[401ffcdb336c4a738bf094f3ce113040.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/eebbc5a7e8f3415bbec8d5c6bc2dd8dd.png
[77578431d1cc4cf1af6632b499942339.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/28b740f490a747e68e28d75c9eddbe5d.png
[34d208abc1864079901b12daff27c48b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/91567cca6f864d968b4a370333d7ef8b.png
[b8b0d3d13b754bd2b1128fb40741b6fb.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/a4dc311269d440be833a8f23e5dfcc08.png
[f048b61b8bfa41ee98933353adf18be2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/44b5ffc72ff940b0bbbf4ca5df967e9b.png
[a1739f6c8ced4ae794a7da990e3bcfb8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/7119f0ce77744f5d9877d6b327ac6bd4.png