Binary Tree Preorder Traversal
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public class Solution {
public ArrayList<Integer> preorderTraversal(TreeNode root) {
ArrayList<Integer> returnList = new ArrayList<Integer>();
if(root == null)
return returnList;
Stack<TreeNode> stack = new Stack<TreeNode>();
stack.push(root);
while(!stack.empty()){
TreeNode n = stack.pop();
returnList.add(n.val);
if(n.right != null){
stack.push(n.right);
}
if(n.left != null){
stack.push(n.left);
}
}
return returnList;
}
}
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
// method 2: iteration
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;
}
Morris Preorder Iterative
- 如果当前节点的左孩子为空，则输出当前节点并将其右孩子作为当前节点。
- 如果当前节点的左孩子不为空，在当前节点的左子树中找到当前节点在中序遍历下的前驱节点。
A>如果前驱节点的右孩子为空，将它的右孩子设置为当前节点。输出当前节点（在这里输出，这是与中序遍历唯一一点不同）。当前节点更新为当前节点的左孩子。
B>如果前驱节点的右孩子为当前节点，将它的右孩子重新设为空。当前节点更新为当前节点的右孩子。
- 重复以上1、2直到当前节点为空。
void preorderMorrisTraversal(TreeNode root) {
TreeNode cur = root, prev = null;
while (cur != null){
if (cur.left == null){
printf("%d ", cur.val);
cur = cur.right;
}else{
prev = cur.left;
while (prev.right != null && prev.right != cur)
prev = prev.right;
if (prev.right == null){
printf("%d ", cur.val); // the only difference with inorder-traversal
prev.right = cur;
cur = cur.left;
}else{
prev.right = null;
cur = cur.right;
}
}
}
}