94. Binary Tree Inorder Traversal

naive级别递归三连其二：中序遍历。

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    dfs(root, res);
    return res;
}

public void dfs(TreeNode root, List<Integer> res) {
    if (root == null) return;

    dfs(root.left, res);
    res.add(root.val);
    dfs(root.right, res);
}

递归的理解：同样先写出三个点的中序遍历，然后发现迷之缩进里的两个左右子树的if可以用dfs复用。

public void dfs(TreeNode root, List<Integer> res) {
    if (root == null) return;
        // 左边的坑：dfs(root.left, res);
        if (root.left == null) return;
        res.add(root.left.val);
    res.add(root.val);
        // 右边的坑：dfs(root.right, res)
        if (root.right == null) return;
        res.add(root.right.val);
}

注意不要用Stack。中序遍历的栈实现中有一个指针，一开始栈为空，或者有时候栈空的时候指针还指着下一个点，如[1,null,2,3]，所以判断条件为是栈不为空或者指针不为空。

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode node = root;

    while (!stack.isEmpty() || node != null) {
        while (node != null) {
            stack.push(node);
            node = node.left;
        }
        node = stack.pop();
        res.add(node.val);
        node = node.right;
    }
    return res;
}