94. Binary Tree Inorder Traversal

Binary Tree Inorder Traversal - LeetCodeLeetCode

1. iterative

若 cur 不為 null

一路走左, 更新 cur 為左

到底了 => pop(), 塞值,

檢查右邊有無元素

有: 又一路走左

無: pop() 塞值

反覆...

O(n), O(n)

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        
        Stack<TreeNode> stack = new Stack<>();
        
        TreeNode cur = root;
        
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            cur = stack.pop();
            res.add(cur.val);
            cur = cur.right;
        }
        return res;
    }
}

or like this

只有外面有 while, 好像比較合理, 概念一樣

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

}

2. recursion

時間複雜度：O （n ）。

空間複雜度：最壞情況下需要空間上O （n ），平均情況為O（ log n）。

this is more clean

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        helper(root, res);
        return res;
    }
    private void helper (TreeNode root, List<Integer> res) {
        if (root == null) return;
        helper(root.left, res);
        res.add(root.val);
        helper(root.right, res);
    }
}