Given a binary tree, return the in-order traversal of its nodes' values
Iterative: Using Stack-Time: O(n), Space: O(logn)
We can take advantage of the empty right child of in-order predecessor of current node.
From http://www.cnblogs.com/TenosDoIt/p/3445449.html
Recursive
Read full article from LeetCode - Binary Tree Inorder Traversal | Darren's Blog
Iterative: Using Stack-Time: O(n), Space: O(logn)
public ArrayList<Integer> inorderTraversal(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);
p = p.left;
} else { // Left subtree has been traversed, add the value of current node, and go to its right subtree
p = stack.pop();
result.add(p.val);
p = p.right;
}
}
return result;
}
Morris TraversalWe can take advantage of the empty right child of in-order predecessor of current node.
From http://www.cnblogs.com/TenosDoIt/p/3445449.html
关于Morris Traversal算法，他是基于线索二叉树，它利用二叉树节点中闲置的右指针指向该节点在中序序列中的后缀节点。该算法的空间复杂度为O(1)
文中给出算法步骤如下：
1. Initialize current as root
2. While current is not NULL
If current does not have left child
a) Print current’s data
b) Go to the right, i.e., current = current->right
Else
a) Make current as right child of the rightmost node in current's left subtree
b) Go to this left child, i.e., current = current->left
重复以下1、2直到当前节点为空。
1. 如果当前节点的左孩子为空，则输出当前节点并将其右孩子作为当前节点。
2. 如果当前节点的左孩子不为空，在当前节点的左子树中找到当前节点在中序遍历下的前驱节点（即当前节点的左子树的最右节点）。
a) 如果前驱节点的右孩子为空，将它的右孩子设置为当前节点（利用这个空的右孩子指向它的后缀）。当前节点更新为当前节点的左孩子。
b) 如果前驱节点的右孩子为当前节点，将它的右孩子重新设为空（恢复树的形状）。输出当前节点。当前节点更新为当前节点的右孩子。
public ArrayList<Integer> inorderTraversal(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);
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;
p = p.left;
} else { // Its left subtree has been traversed; recover tree structure
q.right = null;
result.add(p.val);
p = p.right;
}
}
}
return result;
}
Recursive
public ArrayList<Integer> inorderTraversal(TreeNode root) {
ArrayList<Integer> result = new ArrayList<Integer>();
recursiveInorderTraversal(root, result);
return result;
}
private void recursiveInorderTraversal(TreeNode root, ArrayList<Integer> result) {
if (root == null)
return;
recursiveInorderTraversal(root.left, result);
result.add(root.val);
recursiveInorderTraversal(root.right, result);
}
Read full article from LeetCode - Binary Tree Inorder Traversal | Darren's Blog
No comments:
Post a Comment