[LeetCode] Populating Next Right Pointers in Each Node I, II

Populating Next Right Pointers in Each Node I

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.

Note:

• You may only use constant extra space.
• You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).

For example,
Given the following perfect binary tree,

         1
       /  \
      2    3
     / \  / \
    4  5  6  7

After calling your function, the tree should look like:

         1 -> NULL
       /  \
      2 -> 3 -> NULL
     / \  / \
    4->5->6->7 -> NULL

Populating Next Right Pointers in Each Node II

Follow up for problem "Populating Next Right Pointers in Each Node".

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

思路：

能解II的算法必然能解I，所以这里只讨论II的解。

递推：在第i层的所有next pointer都连接好的情况下，如何连接第i+1层的next pointer?
显然从第i层的最左节点开始依次通过next pointer遍历这一层，同时将他们的children，即第i+1层的节点依次通过next pointer连接起来。连接的时候要分情况处理。

初始情况：对于顶层，只有一个节点root，所以该层连接已经完成。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

class Solution { public: void connect(TreeLinkNode *root) { while(root && !root->left && !root->right) root = root->next; if(!root) return; TreeLinkNode *leftMost = root->left ? root->left : root->right; TreeLinkNode *cur = leftMost; while(root) { if(cur==root->left) { if(root->right) { cur->next = root->right; cur = cur->next; } root = root->next; } else if(cur==root->right) { root = root->next; } else { // cur is the child of the previous node of root if(!root->left && !root->right) { root = root->next; continue; } cur->next = root->left ? root->left : root->right; cur = cur->next; } } connect(leftMost); } };

递归不是constant space的，也可以写成迭代解：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35

class Solution { public: void connect(TreeLinkNode *root) { TreeLinkNode *leftMost = root; while(leftMost) { root = leftMost; while(root && !root->left && !root->right) root = root->next; if(!root) return; leftMost = root->left ? root->left : root->right; TreeLinkNode *cur = leftMost; while(root) { if(cur==root->left) { if(root->right) { cur->next = root->right; cur = cur->next; } root = root->next; } else if(cur==root->right) { root = root->next; } else { // cur is the child of the previous node of root if(!root->left && !root->right) { root = root->next; continue; } cur->next = root->left ? root->left : root->right; cur = cur->next; } } } } };

[LeetCode] Binary Tree Zigzag Level Order Traversal

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]
]

思路：

Binary Tree Level Order Traversal那题的变种。一样的层序访问，区别仅仅在于访问是左向右，右向左交替进行。

1. 用两个stack来存储curLevel和nextLevel的节点可以实现这样的左右顺序反转。因为stack是先进后出的，节点push进stack的顺序和pop出stack的顺序正好是相反的：

假设stack curLevel pop出的第一个节点是该层的最左节点x，压入x->left和x->right进stack nextLevel。这样依次类推，等整个curLevel的节点都pop出来后，x->left和x->right在nextLevel的最底部。当之后开始pop nextLevel时，最后才pop到x->left和x->right。换句话说，curLevel第一个被访问到的节点的子节点，将在nextLevel中最后被访问到。

2. 这里还需注意的是push left/right child进nextLevel的顺序。当curLevel从左向右访问时，应当先push(x->left)再push(x->right)，反之则应该先push(x->right)再push(x->left)。实现时可以用一个bool变量left2right来表示顺序，每访问完一层后反转left2right的值。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40

class Solution { public: vector<vector<int> > zigzagLevelOrder(TreeNode *root) { vector<vector<int>> levelNodeValues; if(!root) return levelNodeValues; stack<TreeNode*> *curLevel = new stack<TreeNode*>(); stack<TreeNode*> *nextLevel = new stack<TreeNode*>(); curLevel->push(root); bool left2right = true; while(!curLevel->empty()) { vector<int> curLevelValues; while(!curLevel->empty()) { TreeNode *cur = curLevel->top(); curLevel->pop(); curLevelValues.push_back(cur->val); if(left2right) { if(cur->left) nextLevel->push(cur->left); if(cur->right) nextLevel->push(cur->right); } else { if(cur->right) nextLevel->push(cur->right); if(cur->left) nextLevel->push(cur->left); } } levelNodeValues.push_back(curLevelValues); // swap curLevel and nextLevel, no need to clear since curLevel is already empty stack<TreeNode*> *temp = curLevel; curLevel = nextLevel; nextLevel = temp; left2right = !left2right; } return levelNodeValues; } };

[LeetCode] Binary Tree Level Order Traversal I, II

Binary Tree Level Order Traversal

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).

For example:
Given binary tree {3,9,20,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

return its level order traversal as:

[
  [3],
  [9,20],
  [15,7]
]

Binary Tree Level Order Traversal II

Given a binary tree, return the bottom-up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root).

For example:
Given binary tree {3,9,20,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

return its bottom-up level order traversal as:

[
  [15,7],
  [9,20],
  [3]
]

思路：

这两题实际是一回事，考察的都是树的层序访问。无非就是在I得到结果后做一次reverse就能得到II要求的结果。无论是树还是图，层序访问最直接的方法就是BFS。

1. BFS可以用一个queue实现，但是难以跟踪每个节点究竟是在第几层。解决办法是除了压入节点指针外，还同时压入节点所在的层数，即压入pair<TreeNode*, int>。

2. 层序访问更直接的方法是将当前层的节点和下一层的节点分别保存在两个container curLevel和nextLevel中（vector, queue, stack都可以，取决于具体要求）。每次扫描curLevel中的节点，并将其左右子节点更新到nextLevel中。当curLevel所有节点扫描过后，该层已经遍历完整，swap curLevel和nextLevel即可继续访问。


1. 两个container的迭代解法

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

class Solution { public: vector<vector<int> > levelOrder(TreeNode *root) { vector<vector<int>> levelNodeValues; if(!root) return levelNodeValues; vector<TreeNode*> *curLevel = new vector<TreeNode*>(); vector<TreeNode*> *nextLevel = new vector<TreeNode*>(); curLevel->push_back(root); while(!curLevel->empty()) { // scan curLevel, collect values of curLevel nodes, and generate nextLevel vector<int> curLevelValues; for(int i=0; i<curLevel->size(); i++) { TreeNode *curNode = (*curLevel)[i]; curLevelValues.push_back(curNode->val); if(curNode->left) nextLevel->push_back(curNode->left); if(curNode->right) nextLevel->push_back(curNode->right); } levelNodeValues.push_back(curLevelValues); //swap curLevel and nextLevel, and clear nextLevel vector<TreeNode*> *temp = curLevel; curLevel = nextLevel; nextLevel = temp; nextLevel->clear(); } return levelNodeValues; } };

2. 单个queue的迭代解法

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

class Solution { struct levelNode { TreeNode *node; int level; levelNode(TreeNode *nd, int lvl):node(nd), level(lvl){} }; public: vector<vector<int> > levelOrder(TreeNode *root) { vector<vector<int>> levelNodeValues; if(!root) return levelNodeValues; queue<levelNode> q; q.push(levelNode(root,0)); while(!q.empty()) { levelNode curLevelNode = q.front(); TreeNode *curNode = curLevelNode.node; int curLevel = curLevelNode.level; q.pop(); if(curLevel==levelNodeValues.size()) levelNodeValues.push_back(vector<int>(0,0)); levelNodeValues[curLevel].push_back(curNode->val); if(curNode->left) q.push(levelNode(curNode->left,curLevel+1)); if(curNode->right) q.push(levelNode(curNode->right,curLevel+1)); } return levelNodeValues; } };

注意ln 22-23需要检查当前节点是否在新的一层，如果是新的一层第一个节点，则要相应增加levelNodeValues的尺寸。

3. 层尾标记法

同样用一个queue来进行BFS，但queue的元素仅为TreeNode*而不需要存储节点的层数。在每一层访问完毕时push一个NULL进queue作为一层结束的标记。这种方法的对于平衡binary tree来说增加了log(n)次的push(NULL)和pop()。但如果是非平衡二叉树的极端情况，可能会增加n次的push和pop。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

class Solution { public: vector<vector<int> > levelOrder(TreeNode *root) { vector<vector<int>> levelNodeValues; if(!root) return levelNodeValues; queue<TreeNode*> q; q.push(root); q.push(NULL); int curLevel = 0; while(!q.empty()) { TreeNode *cur = q.front(); q.pop(); if(!cur) { curLevel++; if(!q.empty()) q.push(NULL); continue; } if(curLevel==levelNodeValues.size()) levelNodeValues.push_back(vector<int>(0,0)); levelNodeValues[curLevel].push_back(cur->val); if(cur->left) q.push(cur->left); if(cur->right) q.push(cur->right); } return levelNodeValues; } };

注意：
ln 9：在压入root后，需要额外压入一个NULL来标记第0层尾。
ln 18：只有在q不为空时才压入层尾标记NULL。少了这个判断，则在处理最后一个NULL时会陷入死循环——不断取出一个NULL，再压回一个NULL。
ln 22-23：和方法2中一样，对新的一层要扩展levelNodeValues的尺寸。

对于Binary Tree Level Order Traversal II，只需要再I的解的基础上，最后再翻转levelNodeValues即可：

1	reverse(levelNodeValues.begin(),levelNodeValues.end());