树的三种DFS遍历，是指按照根节点(自己)被访问的顺序
- Pre-Order： 先访问根节点，再访问其左右子树。对每一个subtree，同样适用。
- In-Order： 先访问其左，再中间，再右子树。对每一个subtree，同样适用。
- Post-Order： 先访问其左右子树，再中间。对每一个subtree，同样适用。
image.png
Pre-Order Traversal
三种解法：
- Recursive
- Iterate 用Stack
- Morris Traversal （好处是，Pre-Order和In-Order代码只有很小的改动）
Morris Pre-Order Traversal (LeetCode 144) (Medium)
1...If left child is null, print the current node data. Move to right child.
….Else, Make the right child of the inorder predecessor point to the current node. Two cases arise:
………a) The right child of the inorder predecessor already points to the current node. Set right child to NULL. Move to right child of current node.
………b) The right child is NULL. Set it to current node. Print current node’s data and move to left child of current node.
2...Iterate until current node is not NULL.
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new LinkedList<> ();
TreeNode current = root;
TreeNode prev = null;
while (current != null) {
if (current.left == null) {
result.add (current.val);
current = current.right;
} else { // has left, then find the rightmost of left subtree and connect to current
prev = current.left;
while (prev.right != null && prev.right != current) {
prev = prev.right;
}
// difference from in-order: print current first
if (prev.right == null) {
result.add (current.val);
prev.right = current;
current = current.left;
} else {
prev.right = null;
current = current.right;
}
}
}
return result;
}
}
Morris In-Ordere Traversal (LeetCode 94) (Medium)
- Initialize current as root
- 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
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new LinkedList<> ();
TreeNode current = root;
TreeNode prev = null;
while (current != null) {
// left first
if (current.left == null) {
result.add (current.val);
current = current.right;
}
// if there is left, get the rightmost node of left subtree and connect back to current
else {
prev = current.left;
// 1. get previous node
// because the prev.right might connected to current already
// need to stop in this case
while (prev.right != null && prev.right != current) {
prev = prev.right;
}
// 2. if previous hasnt connected to current
if (prev.right == null) {
prev.right = current;
current = current.left;
}
// 3. if previous already connected to current, and while traverse current node
// has been visited (only after visited current, we can get the prev)
else if (prev.right == current) {
// revert the tree modification
prev.right = null;
result.add (current.val);
current = current.right;
}
}
}
return result;
}
}
Stack Inorder
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
if (root == null)
return new ArrayList<Integer> ();
TreeNode currentNode = root;
Stack<TreeNode> tracker = new Stack<> ();
List<Integer> result = new ArrayList<> ();
while (currentNode != null || !tracker.isEmpty ()) {
while (currentNode != null) {
tracker.push (currentNode);
currentNode = currentNode.left;
}
TreeNode current = tracker.pop ();
result.add (current.val);
currentNode = current.right;
}
return result;
}
}
Post-Order Traversal** (LeetCode 145) (Hard)
Recursive Solution
- 用reversed post -order traversal
- While root is not EMPTY
- Pop the first element from the stack and push it into a List
- reverse_post (root.right)
- reverse_post (root.left)
- reverse (the result List) === > 就是最后post - order的结果
Stack Solution
while not stack.empty()
root = stack.pop ()
print (root.val)
stack.push (root.left)
stack.push (root.right)
reverse (output)
Note：
实现的时候，不需要最后翻转，可以在用Deque来存储Result List，加入的时候AddFirst.
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
Deque<Integer> result = new LinkedList<> ();
if (root == null) {
return new ArrayList (result);
}
Stack <TreeNode> tracker = new Stack <> ();
tracker.push (root);
while (!tracker.isEmpty ()) {
TreeNode node = tracker.pop ();
result.addFirst (node.val);
if (node.left != null)
tracker.push (node.left);
if (node.right != null)
tracker.push (node.right);
}
return new ArrayList(result);
}
}
