94. Binary Tree Inorder Traversal

Version #3 Very Important
2ND TRY Stack Traversal
We have two operations -> push and pop
push of curr makes sure that all nodes are order by their in-order-traversal order
pop takes that into result list

Since we are doing these two things at the same time, we stop until curr == null && stack.isEmpty()

100.00 %
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
Deque<TreeNode> deque = new ArrayDeque<>();
TreeNode curr = root;
while (curr != null || !deque.isEmpty()) {
while (curr != null) {
deque.addFirst(curr);
curr = curr.left;
}
curr = deque.removeFirst();
result.add(curr.val);
curr = curr.right;
}
return result;
       
    }
}

1ST TRY
Traversal Method
https://www.kancloud.cn/kancloud/data-structure-and-algorithm-notes/73026
参考了这里面说的四步：

1. 首先需要一直对左子树迭代并将非空节点入栈
2. 节点指针为空后不再入栈
3. 当前节点为空时进行出栈操作，并访问栈顶节点
4. 将当前指针p用其右子节点替代

步骤2,3,4对应「左根右」的遍历结构，只是此时的步骤2取的左值为空。

我的理解：
用curr对整个Tree进行遍历
Step1
如果curr不是null，就一直向左找，同时curr入栈。当curr到达null时，它的parent为最左节点，也是最后一个进入stack的node

Step2
此时curr = stack.pop() 获得未访问过的最左节点，对该点进行operation

Step3
对于当前curr来说，可以保证它的左边和它自身都被遍历过了，于是开始搜索它的右边
curr = curr.right
若curr不为null, 则在step1的讨论范围之内
若curr为null，则直接进入step2


public class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        if (root == null) return result;
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode curr = root;
        while (curr != null || !stack.isEmpty()) {
            if (curr != null) {
                stack.add(curr);
                curr = curr.left;
                continue;
            }
            //curr is null
            curr = stack.pop();
            result.add(curr.val);
            curr = curr.right;
        }
        return result;
    }
}

Version #1 Recursion 每一次都new了新的list，效率比较低
44.48%
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        if (root == null) return result;
        List<Integer> left = inorderTraversal(root.left);
        List<Integer> right = inorderTraversal(root.right);
        result.addAll(left);
        result.add(root.val);
        result.addAll(right);
        return result;
    }
}

Version #2 Recursion 把result list 作为一个参数传进了helper函数，以外的是时间并没有提高
44.48%
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        inorderTraversalHelper(root, result);
        return result;
    }
    private void inorderTraversalHelper(TreeNode root, List<Integer> result) {
        if (root == null) return;
        inorderTraversalHelper(root.left, result);
        result.add(root.val);
        inorderTraversalHelper(root.right, result);
    }
}