Tree
- Traversal(周遊)
-
- 基本周遊類型
-
- 1. Inorder(中序)
-
- (1) 遞歸
- (2) 使用棧疊代
- (3) Morris周遊(虛拟節點)
- 2. Preorder( 前序)
-
- (1)遞歸
- (2)使用棧疊代
- (3)Morris周遊
- 3. Postorder( 後序)
-
- (1) 遞歸
- (2) 使用棧疊代
- (3) Morris周遊
- 4. Iterator( 疊代器)
- 5. 類似題目
Traversal(周遊)
基本周遊類型
1. Inorder(中序)
94. Binary Tree Inorder Traversal
Given a binary tree, return the inorder traversal of its nodes’ values.
Example:
Input: [1,null,2,3]
1
\
2
/
3
Output: [1,3,2]
(1) 遞歸
TC: O(n) SC: O(n)
public static void inOrder(Node root) {
if (root == null) return;
inOrder(root.left);
System.out.print(root.val + " ");
inOrder(root.right);
}
(2) 使用棧疊代
解題思路
使用棧以及一個周遊指針
TC: O(n) SC: O(n)
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
if (root == null) return res;
Deque<TreeNode> stk = new ArrayDeque<>();
TreeNode p = root;
while(p != null || !stk.isEmpty()){
if (p != null){
stk.push(p);
p = p.left;
}else if (!stk.isEmpty()){
TreeNode cur = stk.pop();
res.add(cur.val);
p = cur.right;
}
}
return res;
}
(3) Morris周遊(虛拟節點)
解題思路
一般面試考周遊考遞歸或者疊代的算法比較常見，morris周遊比較難，如果想提高印象分可以使用，我會在另一篇部落格中詳細說明這個算法
TC: O(n) SC: O(1)
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
if (root == null) return res;
TreeNode p1 = root;
TreeNode p2 = null;
while(p1 != null){
p2 = p1.left;
if (p2 != null){
while(p2.right != null && p2.right != p1){
p2 = p2.right;
}
if (p2.right == p1){
p2.right = null;
}else{
p2.right = p1;
p1 = p1.left;
continue;
}
}
res.add(p1.val);
p1 = p1.right;
}
return res;
}
2. Preorder( 前序)
Tree: Preorder Traversal
Complete the preOrder function in your editor below, which has parameter: a pointer to the root of a binary tree. It must print the values in the tree’s preorder traversal as a single line of space-separated values.
Input Format
Our hidden tester code passes the root node of a binary tree to your preOrder function.
Constraints
Nodes in the tree
Output Format
Print the tree’s preorder traversal as a single line of space-separated values.
Sample Input
1
\
2
\
5
/ \
3 6
\
4
Sample Output
1 2 5 3 4 6
(1)遞歸
TC:O(n) SC: O(n)
public static void preOrder(Node root) {
if (root == null) return;
System.out.print(root.data + " ");
preOrder(root.left);
preOrder(root.right);
}
(2)使用棧疊代
TC:O(n) SC: O(n)
解題思路
每個節點出棧即列印，子節點從右往左壓棧
public static void preOrder(Node root) {
Deque<Node> stk = new ArrayDeque<>();
stk.push(root);
while(!stk.isEmpty()){
Node cur = stk.pop();
System.out.print(cur.data + " " );
if (cur.right != null) stk.push(cur.right);
if (cur.left != null) stk.push(cur.left);
}
}
(3)Morris周遊
TC:O(n) SC: O(1)
解題思路
和中序周遊相比，如果改節點不存在左孩子則直接列印目前節點
public static void preOrder(Node root) {
if (root == null)return;
Node p1 = root;
Node p2 = null;
while(p1 != null){
p2 = p1.left;
if(p2 != null){
while(p2.right != null && p2.right != p1){
p2 = p2.right;
}
if (p2.right == p1){
p2.right = null;
}else{
System.out.print(p1.data + " ");
p2.right = p1;
p1 = p1.left;
continue;
}
}else{
System.out.print(p1.data + " ");
}
p1 = p1.right;
}
}
3. Postorder( 後序)
Tree: Postorder Traversal
Complete the postOrder function in your editor below, which has parameter: a pointer to the root of a binary tree. It must print the values in the tree’s postorder traversal as a single line of space-separated values.
Input Format
Our hidden tester code passes the root node of a binary tree to your postOrder function.
Constraints
1 Nodes in the tree 500
Output Format
Print the tree’s postorder traversal as a single line of space-separated values.
Sample Input
1
\
2
\
5
/ \
3 6
\
4
Sample Output
4 3 6 5 2 1
(1) 遞歸
TC:O(n) SC: O(n)
public static void postOrder(Node root) {
if (root == null) return;
postOrder(root.left);
postOrder(root.right);
System.out.print(root.val + " ");
}
(2) 使用棧疊代
第一種比較hacky的方式就是利用list的addFirst這個性質。許多轉換周遊順序的題目可以用這個方法修改輸出。但是實際周遊并不是符合題目要求的，有比較較真的面試官會要求實作完全符合周遊要求的算法。
public List<Integer> postorderTraversal(TreeNode root) {
LinkedList<Integer> ans = new LinkedList<>();
Stack<TreeNode> stack = new Stack<>();
if (root == null) return ans;
stack.push(root);
while (!stack.isEmpty()) {
TreeNode cur = stack.pop();
ans.addFirst(cur.val);
if (cur.left != null) {
stack.push(cur.left);
}
if (cur.right != null) {
stack.push(cur.right);
}
}
return ans;
}
這種算法就是完全符合後序周遊，但是也有需要注意的一點，就是如果将指針節點設定為null，那麼當出現子節點的父節點沒有右邊節點時會fail第一個if statement，而這個子節點永遠不會入棧。是以指針節點p必須確定初始的時候不與樹中任何的節點相等。
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
if (root == null) return res;
Deque<TreeNode> stk = new ArrayDeque<>();
stk.push(root);
TreeNode p = new TreeNode(-9999999);
while(!stk.isEmpty()){
TreeNode peak = stk.peek();
if (peak.left != null && p != peak.left && p != peak.right){
stk.push(peak.left);
}else if (peak.right != null && p != peak.right){
stk.push(peak.right);
}else{
res.add(stk.pop().val);
p = peak;
}
}
return res;
}
(3) Morris周遊
解題思路
依次逆序列印右子樹的邊
TC:O(n) SC: O(1)
public static void postOrder(Node root) {
if (root == null)return;
Node p1 = root;
Node p2 = null;
while(p1 != null){
p2 = p1.left;
if(p2 != null){
while(p2.right != null && p2.right != p1){
p2 = p2.right;
}
if (p2.right == p1){
p2.right = null;
printEdge(p1.left);
}else{
p2.right = p1;
p1 = p1.left;
continue;
}
}
p1 = p1.right;
}
printEdge(root);
}
private static void printEdge(Node root){
Node tail = reverse(root);
Node cur = tail;
while(cur != null){
System.out.print(cur.data + " ");
cur = cur.right;
}
reverse(tail);
}
private static Node reverse(Node root){
Node pre = null;
Node cur = root;
while(cur != null){
Node next = cur.right;
cur.right = pre;
pre = cur;
cur = next;
}
return pre;
}
4. Iterator( 疊代器)
173. Binary Search Tree Iterator
Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.
Calling next() will return the next smallest number in the BST.
Example:
BSTIterator iterator = new BSTIterator(root);
iterator.next(); // return 3
iterator.next(); // return 7
iterator.hasNext(); // return true
iterator.next(); // return 9
iterator.hasNext(); // return true
iterator.next(); // return 15
iterator.hasNext(); // return true
iterator.next(); // return 20
iterator.hasNext(); // return false
Note:
next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.
You may assume that next() call will always be valid, that is, there will be at least a next smallest number in the BST when next() is called.
其實就是把中序周遊包了一層疊代器的皮，需要把初始壓棧和周遊節點分成兩個部分，符合疊代器的規範就行。
class BSTIterator {
Deque<TreeNode> stk;
TreeNode p;
public BSTIterator(TreeNode root) {
stk = new ArrayDeque<TreeNode>();
p = root;
while(p != null){
stk.push(p);
p = p.left;
}
}
/** @return the next smallest number */
public int next() {
int res = 0;
if (hasNext()){
TreeNode cur = stk.pop();
res = cur.val;
cur = cur.right;
while(cur != null){
stk.push(cur);
cur = cur.left;
}
}
return res;
}
/** @return whether we have a next smallest number */
public boolean hasNext() {
return !stk.isEmpty();
}
}
5. 類似題目
589. N-ary Tree Preorder Traversal
590. N-ary Tree Postorder Traversal
這個就是非常直覺的binary tree traversal的擴充，不同之處僅僅在于左右子節點變成了一個子節點的list。
![Java 八種排序算法總結[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)