Sunday, July 27, 2014

那些年我们一起遍历过的树 -- 遍历树,tree traversal



这篇博文想和大家讨论一下tree的traversal有哪些方法。当然我们都很熟悉DFS(InOrder, PreOrder, PostOrder)和BFS,这篇我们想谈一下一些其他方法以及DFS BFS的变种

[可以识辨每层的BFS]

[细节]
在题目中,我们时常需要做BFS并且要区分树的层与层,然后利用这个信息完成任务

[做法]
使用一个queue
初始化queue里插入root和一个分割符(普通node是pointer,因此分割符可选用特殊数字)
pop出root, 像通常BFS一样遍历root的child node,当dequeue分隔符时,在queue里后面插入分隔符
这样遍历完整棵树

[例题]
Populating Next Right Pointers in Each Node --[From Leetcode]
What if the given tree could be any binary tree? Would your previous solution still work?
Note:
  • You may only use constant extra space.
For example,
Given the following binary tree,
       1
      /  \
     2    3
    / \    \
   4   5    7
After calling your function, the tree should look like:
       1 -> NULL
      /  \
     2 -> 3 -> NULL
    / \    \
   4-> 5 -> 7 -> NULL

[代码]
class Solution {
public:
   void connect(TreeLinkNode *root) {
       // BFS Queue
       vector<TreeLinkNode*> bfsq;
       TreeLinkNode*dummy = new TreeLinkNode(0);
       if (root)
       bfsq.push_back(root);
       bfsq.push_back(dummy);

       while (bfsq.size() > 1)
       {
           if (bfsq[1]!=dummy)
           bfsq.front()->next = bfsq[1];
           if (bfsq.front()==dummy)
           {
               bfsq.push_back(dummy);
           }
           else
           {
               if (bfsq.front()->left)
               bfsq.push_back(bfsq.front()->left);
               if (bfsq.front()->right)
               bfsq.push_back(bfsq.front()->right);
           }
           bfsq.erase(bfsq.begin());
       }
       delete(dummy);
   }
};

[不同方向的BFS]

[细节]
例如在第一层中从左向右遍历每个node,第二层就从右向左遍历,第三层向右...

[做法]
使用两个stackS1,S2
初始化把root插入到S1里
然后pop出root, 在遍历root的child node(s)时放入S2里
pop  S2的时候,把child nodes放入S1里
这样轮流使用两个stack,遍历完整棵树

[例题]
Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).
For example:
Given binary tree {3,9,20,#,#,15,7},
   3
  / \
 9  20
   /  \
  15   7
return its zigzag level order traversal as:
[
 [3],
 [20,9],
 [15,7]
]

[代码]
/**
* Definition for binary tree
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
public class Solution {
   public ArrayList<ArrayList<Integer>> zigzagLevelOrder(TreeNode root) {
       // Start typing your Java solution below
       // DO NOT write main() function
       ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
       if(root==null) return res;
       boolean order = true;
       ArrayList<TreeNode> toVisit = new ArrayList<TreeNode>();
       toVisit.add(root);
       while(!toVisit.isEmpty()){
           ArrayList<TreeNode> next = new ArrayList<TreeNode>();
           ArrayList<Integer> temp = new ArrayList<Integer>();
           for(TreeNode node:toVisit){
               temp.add(node.val);
           }
           res.add(temp);
           for(int i=toVisit.size()-1;i>=0;i--){
               TreeNode node = toVisit.get(i);
               if(order){
                   if(node.right!=null) next.add(node.right);
                   if(node.left!=null) next.add(node.left);
               }else{
                   if(node.left!=null) next.add(node.left);
                   if(node.right!=null) next.add(node.right);
               }
           }
           order = order?false:true;
           toVisit = new ArrayList<TreeNode>(next);
       }
       return res;
   }
}

[Make use of additional pointers in the Tree for traversal]

[细节]
很多题目在树里提供additional pointers(to parent or to sibling),应该首先考虑使用这些additional pointer做traversal

[例题]
Given a binary tree
  struct TreeLinkNode {
     TreeLinkNode *left;
     TreeLinkNode *right;
     TreeLinkNode *next;
   }
Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.
Initially, all next pointers are set to NULL.
[代码]
Basic idea is to make use of the next pointer of the current level, iterate through all the nodes on the current level, meanwhile, populate the next pointers of the children below
// the link of level(i) is the queue of level(i+1)
void connect(TreeLinkNode * n) {
   while (n) {
       TreeLinkNode * next = NULL; // the first node of next level
       TreeLinkNode * prev = NULL; // previous node on the same level
       for (; n; n=n->next) {
           if (!next) next = n->left?n->left:n->right;

           if (n->left) {
               if (prev) prev->next = n->left;
               prev = n->left;
           }
           if (n->right) {
               if (prev) prev->next = n->right;
               prev = n->right;
           }
       }
       n = next; // turn to next level
   }
}

[Bottom up traversal of a tree]


[细节]
我们目前看到的绝大多数题都是从一个树的根节点开始遍历,然后逐层到叶结点。很多时候我们也需要从叶结点开始遍历,到根节点。这样做的好处:
1)得到特殊的遍历顺序,可以用于特别的需要,比如按顺序读一个sorted linked list同时构建BST
2)从叶结点得到很多有用讯息,比如一个特定值是否在当前节点为根的子树存在,或者树的深度等等

[做法]
Recursively visit a tree as you do DFS
However, call the recursive function to left child and right child before you ‘visit’ the root

[例题]
Convert Sorted List to Binary Search Tree

[代码]
Bottom up traversal. The key is call recursion call before you do something about the current node, so that the recursion call chain will finally reach leaf node before you handle the subtree root nodes

public class Solution {
   static ListNode head;
   public TreeNode sortedListToBST(ListNode head) {
       if(head == null) return null;
       this.head = head;
        
       // get list length
       int len = 0;
       ListNode ln = head;
       while(ln != null){
           len++;
           ln = ln.next;
       }  
        
       return sortedListToBST(0, len - 1);
   }
    
   // build bottom-to-top
   public TreeNode sortedListToBST(int start, int end) {
       // if finished (root)
       if(start > end) return null;
        
       // get mid val
       int mid = (start + end) / 2;
        
       // build left sub tree
       TreeNode left = sortedListToBST(start, mid - 1);
       // build root node
       TreeNode root = new TreeNode(head.val);
       root.left = left;
       // move to next node to build right sub tree
       head = head.next;
       root.right = sortedListToBST(mid + 1, end);
        
       return root;
   }
}

[References]

No comments:

Post a Comment