二叉树的迭代遍历

忘是亡心i 2023-10-14 21:15 74阅读 0赞

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

*  思路
 *  前序遍历（迭代法）
 *  中序遍历（迭代法）
 *   *  前序遍历代码不能被中序遍历通用的原因
 *  后序遍历（迭代法）
 *  总结
 *  代码实现
 *   *  1. 前序遍历
     *  2. 中序遍历
     *  3. 后序遍历

# 思路 #

为什么可以用迭代法（非递归的方式）来实现二叉树的前后中序遍历？

**递归的实现就是：每一次递归调用都会把函数的局部变量、参数值和返回地址等压入调用栈中**，然后递归返回的时候，从栈顶弹出上一次递归的各项参数，所以这就是递归为什么可以返回上一层位置的原因。

此时大家应该知道我们用栈也可以是实现二叉树的前后中序遍历了。

# 前序遍历（迭代法） #

前序遍历是中左右，每次先处理的是中间节点，那么先将根节点放入栈中，然后将右孩子加入栈，再加入左孩子。

为什么要先加入右孩子，再加入左孩子呢？ 因为这样出栈的时候才是中左右的顺序。

# 中序遍历（迭代法） #

在迭代过程中，其实是有两个操作的：

1.  处理：将元素放进result数组中
2.  访问：遍历节点

## 前序遍历代码不能被中序遍历通用的原因 ##

前序遍历的顺序是中左右，先访问的元素是中间节点，要处理的元素也是中间节点，所以刚刚才能写出相对简洁的代码，**因为要访问的元素和要处理的元素顺序是一致的，都是中间节点**。

那么再看看中序遍历，中序遍历是左中右，先访问的是二叉树顶部的节点，然后一层一层向下访问，直到到达树左面的最底部，再开始处理节点（也就是在把节点的数值放进result数组中），这就造成了**处理顺序和访问顺序是不一致的**。

那么**在使用迭代法写中序遍历，就需要借用指针的遍历来帮助访问节点，栈则用来处理节点上的元素**。

# 后序遍历（迭代法） #

再来看后序遍历，先序遍历是中左右，后续遍历是左右中，那么我们只需要调整一下先序遍历的代码顺序，就变成中右左的遍历顺序，然后在反转result数组，输出的结果顺序就是左右中了，如下图：  
![在这里插入图片描述][7853e6aec9d347ba957acf3de1bfb240.png]

# 总结 #

此时我们用迭代法写出了二叉树的前后中序遍历，大家可以看出前序和中序是完全两种代码风格，并不像递归写法那样代码稍做调整，就可以实现前后中序。

**这是因为前序遍历中访问节点（遍历节点）和处理节点（将元素放进result数组中）可以同步处理，但是中序就无法做到同步！**

# 代码实现 #

## 1. 前序遍历 ##

遍历顺序：中-左-右，入栈顺序：中-右-左

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

## 2. 中序遍历 ##

遍历顺序: 左-中-右 入栈顺序： 左-右

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;
        }
    }

## 3. 后序遍历 ##

遍历顺序 左-右-中 入栈顺序：中-左-右 出栈顺序：中-右-左， 最后翻转结果

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

**参考资料**：[二叉树的迭代遍历][Link 1]

[7853e6aec9d347ba957acf3de1bfb240.png]: https://img-blog.csdnimg.cn/7853e6aec9d347ba957acf3de1bfb240.png
[Link 1]: https://programmercarl.com/%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E8%BF%AD%E4%BB%A3%E9%81%8D%E5%8E%86.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE