这篇博文想和大家讨论一下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
/ \
2 3
/ \ \
4 5 7
After calling your function, the tree should look like:
1 -> NULL
/ \
2 -> 3 -> NULL
/ \ \
4-> 5 -> 7 -> 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);
}
};
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.
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
}
}
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]
[细节]
我们目前看到的绝大多数题都是从一个树的根节点开始遍历，然后逐层到叶结点。很多时候我们也需要从叶结点开始遍历，到根节点。这样做的好处：
１）得到特殊的遍历顺序，可以用于特别的需要，比如按顺序读一个sorted linked list同时构建ＢＳＴ
２）从叶结点得到很多有用讯息，比如一个特定值是否在当前节点为根的子树存在，或者树的深度等等
[做法]
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
Thank your for your comment! Check out us at https://baozitraining.org/ if you need mock interviews!