Given a binary tree, return the preorder traversal of its nodes' values.
Morris Traversal:O(1) space
Morris Traversal:O(1) space
public ArrayList<Integer> preorderTraversal(TreeNode root) {
ArrayList<Integer> result = new ArrayList<Integer>();
TreeNode p = root, q = null;
while (p != null) {
if (p.left == null) { // Empty left subtree
result.add(p.val); // Access the value of current node
p = p.right;
} else {
// Find in-order predecessor of current node
q = p.left;
while (q.right != null && q.right != p)
q = q.right;
if (q.right == null) { // Its left subtree has not been traversed; link it to its predecessor
q.right = p;
result.add(p.val); // Access the value of current node
p = p.left;
} else { // Its left subtree has been traversed; recover tree structure
q.right = null;
p = p.right;
}
}
}
return result;
}
Iterative: Using Stack
public ArrayList<Integer> preorderTraversal(TreeNode root) {
ArrayList<Integer> result = new ArrayList<Integer>();
if (root == null)
return result;
Deque<TreeNode> stack = new ArrayDeque<TreeNode>(); // Used to restore parents
TreeNode p = root;
while (p != null || !stack.isEmpty()) {
if (p != null) { // Whenever we meet a node, push it into the stack and go to its left subtree
stack.push(p);
result.add(p.val);
p = p.left;
} else { // Left subtree has been traversed, add the value of current node, and go to its right subtree
p = stack.pop();
p = p.right;
}
}
return result;
}
Recursive
private void recursivePreorderTraversal(TreeNode root, ArrayList<Integer> result) {
if (root == null)
return;
result.add(root.val);
recursivePreorderTraversal(root.left, result);
recursivePreorderTraversal(root.right, result);
}
Read full article from LeetCode - Binary Tree Preorder Traversal | Darren's Blog
No comments:
Post a Comment