Tree Basic & Traversal

[xiedaxia1hao]

Sample Trie Questions:

1268. Search Suggestions System

[xiedaxia1hao]

Tree的三种遍历方式：

• 前序遍历
• 中序遍历
• 后序遍历

如果可以用recursive的方法的话，那就没什么意思了，代码很简单，如下：

void preOrder(TreeNode root) {
    if(root == null) return;
    print(root.val);
    preOrder(root.left);
    preOrder(root.right);
}

void inOrder(TreeNode root) {
    if(root == null) return;
    inOrder(root.left);
    print(root.val);
    inOrder(root.right);
}

void postOrder(TreeNode root) {
    if(root == null) return;
    postOrder(root.left);
    postOrder(root.right);
    print(root.val);
}

[xiedaxia1hao]

144. Binary Tree Preorder Traversal

Preorder: root, left, right

如果要去preorder iteratively，我们的思路是：

1. 先把root push到stack里
2. 开始循环loop
3. 把stack最上面得treenode pop出来
4. 把该treenode加到res里
5. 如果右子树不为空，把右子树加到stack里 （注意这里是要先右子树，因为stack是FILO)
6. 如果左子树不为空，把左子树加到stack里
7. 直到循环结束

简单来说，就是：

1. stack.push(root)
2. Loop:
   1. cur = stack.pop()
   2. res.add(cur.val)
   3. stack.push(cur.right) if cur.right != null
   4. stack.push(cur.left) if cur.left != null

代码如下：

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if(root == null) {
            return res;
        }

        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);

        while(!stack.isEmpty()) {
            TreeNode curr = stack.pop();
            res.add(curr.val);

            if(curr.right != null) {
                stack.push(curr.right);
            }

            if(curr.left != null) {
                stack.push(curr.left);
            }
        }

        return res;
    }
}

---

145. Binary Tree Postorder Traversal

postorder如果要直接想的话，会有点难度。

但是我们来思考一下postorder的顺序: left, right, root

我们再来看一下preorder的顺序：root, left, right

我们可以发现 如果我们把postorder的left和right变换一下位置之后，即right, left, root，当前的顺序就是把preorder的顺序reverse一下。

那对于postorder traversal来说，我们也可以采用和preorder一样的方式来traverse。

1. stack.push(root)
2. Loop:
   1. cur = stack.pop()
   2. res.add(0, cur.val)
   3. stack.push(cur.left) if cur.left != null （和preorder相比，这里我们需要把left和right的入栈顺序反一下）
   4. stack.push(cur.right) if cur.right != null

代码如下：

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if(root == null) {
            return res;
        }

        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);

        while(!stack.isEmpty()) {
            TreeNode curr = stack.pop();
            res.add(0, curr.val);

            if(curr.left != null) {
                stack.push(curr.left);
            }

            if(curr.right != null) {
                stack.push(curr.right);
            }
        }

        return res;
    }
}

[xiedaxia1hao]

94. Binary Tree Inorder Traversal

Inorder和preorder和postorder的思路就不太一样了。

因为inorder的顺序是: left, root, right，所以我们需要在当前节点有左子树的情况下，不断把左子树push到我们的stack中，来push完了之后，把我们最顶端的node pop出来并记录，最后我们往该node的右侧接着traversal。

代码简单来说就是：

该题代码如下：

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if(root == null) {
            return res;
        }

        Stack<TreeNode> stack = new Stack<>();
        while(!stack.isEmpty() || root != null) {
            while(root != null) {
                stack.push(root);
                root = root.left;
            }

            root = stack.pop();
            res.add(root.val);
            root = root.right;
        }

        return res;
    }
}