Little_Flower_Fa


小花花的秘密基地

力扣94. 二叉树的中序遍历

  • 2021-08-22
  • 作者 Water-boiled-fish
  • ~3.12K 字
  1. 1. 递归算法
  2. 2. 迭代算法

力扣94. 二叉树的中序遍历题解

给定一个二叉树的根节点 root ，返回它的 中序 遍历。

示例 1：

输入：root = [1,null,2,3]
输出：[1,3,2]

示例 2：

输入：root = []
输出：[]

示例 3：

输入：root = [1]
输出：[1]

示例 4：

输入：root = [1,2]
输出：[2,1]

示例 5：

输入：root = [1,null,2]
输出：[1,2]

提示：

树中节点数目在范围 [0, 100] 内
-100 <= Node.val <= 100

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-inorder-traversal

递归算法

中序遍历，就是需要先遍历二叉树的左子树，然后访问根节点，最后遍历二叉树的右子树

左根右

那么前序遍历和后序遍历就是根左右和左右根，很简单的就懂了

递归写法

只有三步

第一步递归访问它的左子树，直到最后停止访问

第二步输出

第三步递归访问它的右子树

1
2
3
4
5
if (root == null) return;                  (空树直接返回)

traverse(root.left, res); // 递归遍历左子树    (左)
res.add(root.val); // 添加根节点               (根)
traverse(root.right, res); // 递归遍历右子树   (右)

那么前序和后序遍历的过程只需要调换三条语句顺序即可

根据题意需要一个数组来返回，那么我们来封装一下这个函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
         List<Integer> res = new ArrayList<Integer>();//建立一个表单
         traverse(root, res);                        //进行递归
         return res;                                // 返回遍历结果
    }
    public void traverse(TreeNode root, List<Integer> res) {
        if (root == null) return;
  		traverse(root.left, res); // 递归遍历左子树    (左)
  		res.add(root.val); // 添加根节点               (根)
  		traverse(root.right, res); // 递归遍历右子树   (右)
    }
}

结果

迭代算法

那么什么是迭代算法呢，迭代就是模拟递归的过程，显式的保存下来

怎么模拟递归？那么我们需要一个栈来保存运行时的上下文

拿到节点之后先存起来，访问左子树，指针指向左节点，访问到最后，走到尽头之后拿出之前存进去的节点，然后开始访问右节点，同理输出

因为涉及到栈，先进后出，后进先出，所以

1
2
3
前序遍历，出栈顺序：根左右; 入栈顺序：右左根
中序遍历，出栈顺序：左根右; 入栈顺序：右根左
后序遍历，出栈顺序：左右根; 入栈顺序：根右左

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>(); // 数组保存返回数据
        Deque<TreeNode> stk = new LinkedList<TreeNode>(); // 新建栈
        while (root != null || !stk.isEmpty()) { // 节点有数值 或 栈不为空
            if(root != null) { 
                                  //保存当前的上下文，存起来
                stk.push(root);   // 入栈
                root = root.left; // 访问左子树
            }else{
            root = stk.pop(); // pop()：把之前存进去的节点取出
            res.add(root.val); // 在数组添加当前节点
            root = root.right; // 访问右子树
            }
        }
        return res; // 返回结果
    }
}

结果

本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可
最后编辑：2021-08-25