樹的三種DFS遍歷，是指按照根節(jié)點(diǎn)(自己)被訪問(wèn)的順序
- Pre-Order： 先訪問(wèn)根節(jié)點(diǎn)翩伪，再訪問(wèn)其左右子樹着倾。對(duì)每一個(gè)subtree，同樣適用组去。
- In-Order： 先訪問(wèn)其左，再中間步淹，再右子樹从隆。對(duì)每一個(gè)subtree缭裆，同樣適用键闺。
- Post-Order： 先訪問(wèn)其左右子樹，再中間澈驼。對(duì)每一個(gè)subtree辛燥，同樣適用。
image.png
Pre-Order Traversal
三種解法：
- Recursive
- Iterate 用Stack
- Morris Traversal （好處是盅藻，Pre-Order和In-Order代碼只有很小的改動(dòng)）
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的結(jié)果
Stack Solution
while not stack.empty()
root = stack.pop ()
print (root.val)
stack.push (root.left)
stack.push (root.right)
reverse (output)
Note：
實(shí)現(xiàn)的時(shí)候购桑，不需要最后翻轉(zhuǎn)，可以在用Deque來(lái)存儲(chǔ)Result List氏淑，加入的時(shí)候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);
}
}
