LeetCode 94. Binary Tree Inorder Traversal

Problem

LeetCode 94. Binary Tree Inorder Traversal

1. 题目简述

给出一颗二叉树，返回其中序遍历的顺序（List形式），且尽量使用非递归的形式。例如：

Input: [1,null,2,3]
1
 \
  2
 /
3
Output: [1,3,2]  

2. 算法思路

Stack：

递归的形式很好写，普通的中序遍历，这里不再赘述。问题在于非递归（迭代）的形式怎么办。

我们都知道递归其实就是计算完某节点后不断返回上一级的方法，如果用递归达到同样效果，一般都需要使用栈Stack！

遍历过程：

1. 如果某节点存在左子树，压栈，访问左子树（这里压栈的目的是一级一级可以回溯）。
2. 如果节点没有左子树，说明该次访问已经到最底层，出栈，访问该节点，然后判断右子树是否为空，如果为空，继续pop，直至栈为空结束或者右子树不为空，将指针指向该节点的右子树。

Condition Statement：

1. 当且仅当node为null且Stack为空时，循环结束（初次进入循环时，栈为空，但node不为空；当node为空时，一般都是要pop，除了最后）。

3. 解法：

这里提供两种遍历思路：个人倾向于第二种，比较简洁。

1. 判断节点的左子树是否为空

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        Stack<TreeNode> stack = new Stack<TreeNode>();
        List<Integer> list = new ArrayList<Integer>();
        TreeNode node = root;

        while (node != null) { // 下面的循环里保证了node在遍历未结束时不为null
            if (node.left != null) {
                stack.push(node);
                node = node.left;
            } else {
                list.add(node.val);
                while (node.right == null && !stack.isEmpty()) {
                    node = stack.pop();
                    list.add(node.val);
                }
                node = node.right;
            }
        }

        return list;
    }
}

2. 判断节点是否为空

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        Stack<TreeNode> stack = new Stack<TreeNode>();
        List<Integer> list = new ArrayList<Integer>();
        TreeNode node = root;

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

        return list;
    }
}