No.94 二叉树的中序遍历 (Easy)

题目描述

给定二叉树的根结点，返回其中序遍历

思路

思路1：递归

递归的终止条件：当结点为空的时候，返回。

if (root == null) {
    return;
}

递归的功能：将遍历到的结点添加result数组。

完整代码：

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        // 定义并初始化结果数组
        List<Integer> result = new ArrayList<>();
        // 调用递归函数，在其中改变result数组
        traverse(root, result);
        // 返回result数组
        return result;
    }
    // 定义递归函数，核心代码
    // 接收参数，结点root和结果数组result
    public void traverse(TreeNode root, List<Integer> result) {
        // 终止条件，即当最左结点的左结点为空时，返回
        if (root == null) {
            return;
        }
        // 遍历左子树
        traverse(root.left, result);
        // 添加该结点
        result.add(root.val);
        // 遍历右子数
        traverse(root.right, result);
    }
}

递归的优点:

1. 代码简洁，好理解（貌似）

缺点：

1. 递归不好理解
2. 效率问题

思路2：栈

栈的特点：后入先出 、 先入后出。

思路：

1. 依次入栈根结点，根结点的左子树，根结点的左子树的左子树，以此类推，那么在出栈的时候就是先左结点，然后根；
2. 当一个结点的左子树处理完毕时，处理右子树；
3. 中序遍历顺序为左，中， 右，即出栈顺序为左，中，右，出栈时添加到结果数组中。

栈在Java中如何使用？
不用自带的Stack类，而是使用Deque。原因是Stack类有缺陷，官方都推荐使用Deque.。

Deque<TreeNode> stack = new ArrayDeque<>();//
// 入栈
stack.offerLast(root);
// 或者
stack.addLast(root);
// 出栈
stack.pollLast();
// 或者
stack.removeLast();

代码

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        // 初始化要返回的数组
        List<Integer> result = new ArrayList<>();
        // 初始化栈
        Deque<TreeNode> stack = new ArrayDeque();
        // 开始遍历节点
        // 遍历终止条件为，结点为null并且stack为空， 此时表示所有结点都遍历了
        // 如果只判断了root != null, 那么在入栈完所有左结点就会停止循环，此时栈里仍有结点
        // 如果只判断了!stack.isEmpty(), 那么在出栈了所有左子树以后就会停止，此时右子树还未入栈。
        // 因此需要同时判断root != null || !stack.isEmpty();
        while (root != null || !stack.isEmpty()) {
            // 入栈左子树
            if (root != null) {
                stack.offerLast(root);
                root = root.left;
            } else {
                // 如果左子树为空了，那么出栈，并且遍历右子树
                TreeNode temp = stack.pollLast();
                result.add(temp.val);
                root = temp.right;
            }
        }
        return result;
    }
}