94.md

94. 二叉树的中序遍历

递归解法

思路

• 标签：递归
• 中序遍历也叫中根遍历，遍历时，根节点顺序在中间，即左跟右。先根遍历：根左右；后根遍历：左右根。
• 中根遍历最重要的一点是：如果当前节点没有左子树，记录其值。
• 成功使用递归的关键：保证每一个节点的值都会被记录，递归有两个条件：递归条件和基线条件。
• 递归条件：用于函数自己调用自己。这里设置为如果左 / 右子树不为空，递归调用。
• 基线条件：用于保证递归会结束。这里不用设置，因为只要树不是无穷的，递归就能结束。
• 在计算机内部，使用调用栈（Call Stack）来存放函数。调用另一个函数时，当前函数暂停并处于为完成状态，该函数的所有变量的值都还在内存中。
• 时间复杂度：O(n)。走遍每一个元素
• 空间复杂度：O(?)，函数调用栈的高度

代码

// Java
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        traversal(root, list);
        return list;
    }

    private void traversal(TreeNode root, List<Integer> list) {
        if (root != null) {
            if (root.left != null) {
                traversal(root.left, list);
            }
            list.add(root.val); // 如果当前节点没有左子树，记录其值
            if (root.right != null) {
                traversal(root.right, list);
            }
        }
    }
}

// JavaScript
var inorderTraversal = function (root) {
    let list = [];
    traversal(root, list);
    return list;
};

var traversal = function (root, list) {
    if (root !== null) {
        if (root.left !== null) {
            traversal(root.left, list);
        }
        list.push(root.val);
        if (root.right !== null) {
            traversal(root.right, list);
        }
    }
};

画解

非递归解法

思路

• 标签：栈
• 使用递归时，如果没有结合到函数调用栈理解的话，不太好理解
• 在计算机内部，使用调用栈来存放函数，所以可以直接使用栈来实现，更形象
• 具体参考 LeetCode 官方题解 方法二
• 时间复杂度：O(n)