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
\
2
/
3
return[1,2,3]
.
2. Implementation
(1) Morris Tree Traversal
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
if (root == null) {
return res;
}
TreeNode curNode = root, preNode = null;
while (curNode != null) {
if (curNode.left == null) {
res.add(curNode.val);
curNode = curNode.right;
}
else {
preNode = curNode.left;
while (preNode.right != null && preNode.right != curNode) {
preNode = preNode.right;
}
if (preNode.right == null) {
res.add(curNode.val);
preNode.right = curNode;
curNode = curNode.left;
}
else {
preNode.right = null;
curNode = curNode.right;
}
}
}
return res;
}
}
(2) Iteration
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);
TreeNode curNode = null;
while (!stack.isEmpty()) {
curNode = stack.pop();
res.add(curNode.val);
if (curNode.right != null) {
stack.push(curNode.right);
}
if (curNode.left != null) {
stack.push(curNode.left);
}
}
return res;
}
}
3. Time & Space Complexity
(1) Morris Tree Traversal: 时间复杂度: O(n), 空间复杂度: O(1)
(2) Iteration: 时间复杂度: O(n), 空间复杂度: O(h)
Last updated
Was this helpful?