144 Binary Tree Preorder Traversal

144. Binary Tree Preorder Traversal
1. Question
Given a binary tree, return thepreordertraversal of its nodes' values.
For example:
Given binary tree{1,#,2,3},
1
   1
2
    \
3
     2
4
    /
5
   3
Copied!
return[1,2,3].
2. Implementation
(1) Morris Tree Traversal
1
class Solution {
2
    public List<Integer> preorderTraversal(TreeNode root) {
3
        List<Integer> res = new ArrayList<>();
4
​
5
        if (root == null) {
6
            return res;
7
        }
8
​
9
        TreeNode curNode = root, preNode = null;
10
        while (curNode != null) {
11
            if (curNode.left == null) {
12
                res.add(curNode.val);
13
                curNode = curNode.right;
14
            }
15
            else {
16
                preNode = curNode.left;
17
                while (preNode.right != null && preNode.right != curNode) {
18
                    preNode = preNode.right;
19
                }
20
​
21
                if (preNode.right == null) {
22
                    res.add(curNode.val);
23
                    preNode.right = curNode;
24
                    curNode = curNode.left;
25
                }
26
                else {
27
                    preNode.right = null;
28
                    curNode = curNode.right;
29
                }
30
            }
31
        }
32
        return res;
33
    }
34
}
Copied!
(2) Iteration
1
class Solution {
2
    public List<Integer> preorderTraversal(TreeNode root) {
3
        List<Integer> res = new ArrayList<>();
4
​
5
        if (root == null) {
6
            return res;
7
        }
8
​
9
        Stack<TreeNode> stack = new Stack<>();
10
        stack.push(root);
11
        TreeNode curNode = null;
12
​
13
        while (!stack.isEmpty()) {
14
            curNode = stack.pop();
15
            res.add(curNode.val);
16
​
17
            if (curNode.right != null) {
18
                stack.push(curNode.right);
19
            }
20
​
21
            if (curNode.left != null) {
22
                stack.push(curNode.left);
23
            }
24
        }
25
        return res;
26
    }
27
}
Copied!
3. Time & Space Complexity
(1) Morris Tree Traversal: 时间复杂度: O(n), 空间复杂度: O(1)
(2) Iteration: 时间复杂度: O(n), 空间复杂度: O(h)

124 Binary Tree Maximum Path Sum

145 Binary Tree Postorder Traversal

Last modified 2yr ago

Copy link

Contents

144. Binary Tree Preorder Traversal

1. Question

2. Implementation

3. Time & Space Complexity