94.二叉树的中序遍历

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

示例 1：

img

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

Solution：递归

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    ArrayList<Integer> list=new ArrayList <>();
    public List<Integer> inorderTraversal(TreeNode root) {
    if(root==null){
        return list;
    }
    inorderTraversal(root.left);
    list.add(root.val);
    inorderTraversal(root.right);
    return list;
    }
}

tips：逆中序遍历：右—->根—->左

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public void reverseInorder(TreeNode root) {
        if (root == null) {
            return;
        }
        // 递归遍历右子树
        reverseInorder(root.right);
        // 访问根节点
        System.out.print(root.val + " ");
        // 递归遍历左子树
        reverseInorder(root.left);
    }
}

Solution1: 栈

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
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()) {
            // 尽可能地向左走，并将沿途的节点压入栈中。
            while (root != null) {
                stk.push(root);
                root = root.left;
            }
            // 当无法继续向左时，从栈中取出节点，这是按照中序遍历的顺序访问的节点。
            root = stk.pop();
            // 将节点的值添加到结果列表中。
            res.add(root.val);
            // 转向访问节点的右子树。
            root = root.right;
        }
        // 返回中序遍历的结果列表。
        return res;
    }
}