喜刷刷: binary tree

Showing posts with label binary tree. Show all posts

Wednesday, November 26, 2014

[LeetCode] Unique Binary Search Trees I, II

Unique Binary Search Trees I

Given n, how many structurally unique BST's (binary search trees) that store values 1...n?

For example,
Given n = 3, there are a total of 5 unique BST's.

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

Unique Binary Search Trees II

Given n, generate all structurally unique BST's (binary search trees) that store values 1...n.

For example,
Given n = 3, your program should return all 5 unique BST's shown below.

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

思路: Unique Binary Search Trees I

首先注意这里是BST而不是普通的Binary Tree，所以数字会对插入的位置有影响。这类找combination/permutation的题都需要找找规律。

n = 0

n = 1

n = 2

1 2

\ /

2 1

n = 3

1 3 3 2 1

\ / / / \ \

3 2 1 1 3 2

/ / \ \

2 1 2 3

定义f(n)为unique BST的数量，以n = 3为例：

构造的BST的根节点可以取{1, 2, 3}中的任一数字。

如以1为节点，则left subtree只能有0个节点，而right subtree有2, 3两个节点。所以left/right subtree一共的combination数量为：f(0) * f(2) = 2

以2为节点，则left subtree只能为1，right subtree只能为2：f(1) * f(1) = 1

以3为节点，则left subtree有1, 2两个节点，right subtree有0个节点：f(2)*f(0) = 2

总结规律：

f(0) = 1

f(n) = f(0)*f(n-1) + f(1)*f(n-2) + ... + f(n-2)*f(1) + f(n-1)*f(0)

class Solution {
public:
    int numTrees(int n) {
        vector<int> numBST(n+1,0);
        numBST[0] = 1;
        
        for(int i=1; i<=n; i++) {
            for(int j=0; j<i; j++) {
                numBST[i] += numBST[j]*numBST[i-1-j];
            }
        }
        return numBST[n];
    }
};

思路: Unique Binary Search Trees II

要求生成所有的unique BST，类似combination/permutation的题目，可以递归构造。

1. 根节点可以任取min ~ max (例如min = 1, max = n)，假如取定为i。

2. 则left subtree由min ~ i-1组成，假设可以有L种可能。right subtree由i+1 ~ max组成，假设有R种可能。生成所有可能的left/right subtree。

3 对于每个生成的left subtree/right subtree组合<T_left(p), T_right(q)>，p = 1...L，q = 1...R，添加上根节点i而组成一颗新树。

class Solution {
public:
    vector<TreeNode *> generateTrees(int n) {
        return genBST(1, n);
    }
    
    vector<TreeNode *> genBST(int min, int max) {
        vector<TreeNode *> ret;
        if(min>max) {
            ret.push_back(NULL);
            return ret;
        }
        
        for(int i=min; i<=max; i++) {
            vector<TreeNode*> leftSubTree = genBST(min,i-1);
            vector<TreeNode*> rightSubTree = genBST(i+1,max);
            for(int j=0; j<leftSubTree.size(); j++) {
                for(int k=0; k<rightSubTree.size(); k++) {
                    TreeNode *root = new TreeNode(i);
                    root->left = leftSubTree[j];
                    root->right = rightSubTree[k];
                    ret.push_back(root);
                }
            }
        }
        
        return ret;
    }
};

Monday, November 17, 2014

[LeetCode新题] Binary Tree Upside Down

Given a binary tree where all the right nodes are either leaf nodes with a sibling (a left node that shares the same parent node) or empty, flip it upside down and turn it into a tree where the original right nodes turned into left leaf nodes. Return the new root.

For example:
Given a binary tree {1,2,3,4,5},

return the root of the binary tree [4,5,2,#,#,3,1].

思路：

LeetCode最近出了收费模式的新题，需要买他们出的电子书才能做。不过既然已经免费使用了它家这么多资源，就当买本书做点贡献。

这题第一眼看上去觉得没头绪，不知道怎么上下翻转和左右翻转。但在纸上画几个例子就清楚了。以题目的例子来解释：

1. 对于一个parent来说，加入有right node，必须得有left node。而有left node，right node可以为空。而right node必须为叶子节点。所以该树每层至多有2个节点，并且2节点有共同的parent。

2. 所以对于最底层来说，必有一个left node，而这个left node则为整个新树的根 —— 例子中的4为最底层的左节点，最后成为新树的root。

3. 原树的根节点，变为了新树的最右节点。

3. 对于子树1 2 3来说，需要在以2为根的子树2 4 5建立成新树4 5 2后，插入到新树的最右节点2下面。原树的根节点root为left child，原树root->right为新树的left nnode

递归实现：

class Solution {
public:
    TreeNode *upsideDownBinaryTree(TreeNode *root) {
        TreeNode *temp, *newRoot = NULL;
        temp = buildUpsideDownBT(root, newRoot);
        return newRoot;
    }
    
    TreeNode *buildUpsideDownBT(TreeNode *root, TreeNode *&newRoot) {
        if(!root) return root;
        if(!root->left && !root->right) {
            newRoot = root;
            return root;
        }
        TreeNode *parent = buildUpsideDownBT(root->left, newRoot);
        parent->left = root->right;
        parent->right = root;
        root->left = root->right = NULL;
        return parent->right;
    }
};

总结：
1. 这个递归的核心是，每次建立好一个新的子树后，要返回新子树的最右节点（ln 19)，以便上层的节点可以接回到这个节点的下面。
2. 但如果只返回最右节点，则我们无法知道最后整个新树的根在哪里。所以再base case里必须给新根赋值(ln 12)
3. 每次需要reset最右节点的left/right node，否则最后一层递归，递归到例子中的1节点时，返回前1节点的left/right node仍然为原来的值，而并不为NULL。

Wednesday, November 12, 2014

[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,

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,

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，所以该层连接已经完成。

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的，也可以写成迭代解：

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] Convert Sorted List to Binary Search Tree

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

思路：
非常巧妙的题目，解答时参考了这篇文章： http://leetcode.com/2010/11/convert-sorted-list-to-balanced-binary.html

这题和Convert Sorted Array to Binary Search Tree那题看上去很像，但是从array变成了linked list，就不能O(1)寻找中间节点了。一种直接的修改就是每次遍历一半的节点来找寻中间节点。如何在不知道linked list总长的情况下遍历一半节点？双指针策略，快指针一次走2个节点，慢指针一次走1个节点，当快指针到尾部时，慢指针对应的即为中间节点。但这种方法的时间复杂度为O(N logN)：每层递归一共访问N/2个节点，一共log N层递归（对应树的高度）。

对于构建N节点的binary tree来说理论上算法复杂度最少只能到O(N)，因为生成N个节点本身就需要O(N)。要达到O(N)复杂度的算法，就不能反复遍历来查找中间节点，而只能顺序边访问linked list边构建树。这里的关键是利用构建left subtree的递归，来找寻middle节点。即构建left subtree的时候需要返回两个值：left subtree的root节点，以及整个left subtree在linked list中的下一个节点，即middle节点，也是整个left subtree的parent节点。

class Solution {
public:
    TreeNode *sortedListToBST(ListNode *head) {
        int listLen = 0;
        ListNode *cur = head;
        while(cur) {
            listLen++;
            cur = cur->next;
        }
        return sortedListToBST(head, 0, listLen-1);
    }
    
    TreeNode *sortedListToBST(ListNode *&head, int start, int end) {
        if(start>end) return NULL;
        int mid = start + (end-start)/2;
        TreeNode *leftChild = sortedListToBST(head, start, mid-1);
        TreeNode *root = new TreeNode(head->val);
        head = head->next;
        TreeNode *rightChild = sortedListToBST(head, mid+1, end);
        root->left = leftChild;
        root->right = rightChild;
        return root;
    }
};

总结：

这个方法非常不容易理解

TreeNode *sortedListToBST(ListNode *&head, int start, int end)

这个函数所做的是将*head为头的linked list构建成一个BST，然后返回BST的root，而同时，也将head移动到linked list中第end+1个节点。因为*head既是输入参数，也是返回参数，所以这里用到了指针的引用*&head。注意不能错写成了&*head。理解*&的方法是从右向左读：首先是一个引用，然后是一个对指针的引用，最后是一个对ListNode指针的引用。

那么当left subtree构建完成后，head指向了mid，构建mid树节点。然后后移head到right subtree在linked list中的头节点。继续递归构建right subtree.

跑一个例子：

linked list: 0->1->2->NULL

call (head(0), 0, 2)

mid = 1

node(1), head(2)

/ \

call (head(0), 0, 0) call (head(2), 2, 2)

mid = 0 mid = 2

node(0), head(1) node(2), head(NULL)

/ \ / \

call (head(0), 0, -1) call (head(0), 1, 0) call (head(2), 2, 1) call (head(0), 2, 1)

return NULL return NULL return NULL return NULL

最终结果：

/ \

0 2

Tuesday, November 11, 2014

[LeetCode] Convert Sorted Array to Binary Search Tree

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

思考：

简单秒杀题。要BST平衡，自然要使每个节点的左右子树的大小尽可能接近。队列已经排序过，所以很自然可以取中间的数字为根节点。左半队列 < 中间数字 < 右边队列，符合BST的条件。然后分制递归来构建左右子树。

class Solution {
public:
    TreeNode *sortedArrayToBST(vector<int> &num) {
        return arrayToBST(num, 0, num.size()-1);
    }
    
    TreeNode *arrayToBST(vector<int> &num, int start, int end) {
        if(start>end) return NULL;
        int mid = start + (end-start)/2;
        TreeNode *root = new TreeNode(num[mid]);
        root->left = arrayToBST(num, start, mid-1);
        root->right = arrayToBST(num, mid+1, end);
        return root;
    }
};

[LeetCode] Flatten Binary Tree to Linked List

Given a binary tree, flatten it to a linked list in-place.

For example,
Given

The flattened tree should look like:

解法1：preorder traversal

从题目的例子马上发现其实就是preorder transverse整个tree，然后根据这个访问顺序，后访问到的节点成为先访问到的节点的右子节点。那么最不动脑的方法就是preorder transverse的时候把整个节点序列保存在一个vector中。最后再依次连起来。这个解法的空间复杂度包括了递归深度O(log n)和vector的空间O(n)，所以总的空间复杂度是O(n)。

class Solution {
public:
    void flatten(TreeNode *root) {
        if(!root) return;
        vector<TreeNode*> allNodes;
        preorder(root, allNodes);
        int n = allNodes.size();
        for(int i=0; i<n-1; i++) {
            allNodes[i]->left = NULL;
            allNodes[i]->right = allNodes[i+1];
        }
        allNodes[n-1]->left = allNodes[n-1]->right = NULL;
    }
    
    void preorder(TreeNode *root, vector<TreeNode*> &allNodes) {
        if(!root) return;
        allNodes.push_back(root);
        preorder(root->left, allNodes);
        preorder(root->right, allNodes);
    }
};

解法2：递归构建

假设某节点的左右子树T(root->left)和T(root->right)已经flatten成linked list了：

1
/ \
2 5
\ \
3 6 <- rightTail
\
4 <- leftTail

如何将root、T(root->left)、T(root->right) flatten成一整个linked list？显而易见：

temp = root->right
root->right = root->left
root->left = NULL
leftTail->right = temp

这里需要用到已经flatten的linked list的尾部元素leftTail, rightTail。所以递归返回值应该是生成的整个linked list的尾部。

class Solution {
public:
    void flatten(TreeNode *root) {
        TreeNode* rightTail = flattenBT(root);
    }
    
    TreeNode* flattenBT(TreeNode* root) {
        if(!root) return NULL;
        TreeNode *leftTail = flattenBT(root->left);
        TreeNode *rightTail = flattenBT(root->right);
        if(root->left) {
            TreeNode *temp = root->right;
            root->right = root->left;
            root->left = NULL;
            leftTail->right = temp;
        }
        
        if(rightTail) return rightTail;
        if(leftTail) return leftTail;
        return root;
    }
};

需注意几个细节
ln 11：只有当左子树存在时才将它插入右子树中
ln 18-20：返回尾部元素时，需要特殊处理 (1) 有右子树的情况，(2) 无右子树但有左子树的情况，(3)左右子树均不存在的情况。

[LeetCode] Construct Binary Tree from Inorder and Postorder Traversal

Given inorder and postorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

思路：

和Construct Binary Tree from Preorder and Inorder Traversal雷同，关键在于在inorder中找root，从而得以分割left/right subtree，并通过递归来重构。区别仅仅在于对postorder来说root为序列最后一个节点，以及left/right subtree左右边界index的计算稍有不同。

class Solution {
public:
    TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) {
        if(inorder.size()!=postorder.size()) return NULL;
        int n = inorder.size();
        return buildBT(inorder, postorder, 0, n-1, 0, n-1);
    }
    
    TreeNode *buildBT(vector<int> &inorder, vector<int> &postorder, int s1, int e1, int s2, int e2) {
        if(s1>e1 || s2>e2) return NULL;
        TreeNode *root = new TreeNode(postorder[e2]);
        int rootIndex = -1;
        for(int i=s1; i<=e1; i++) {
            if(inorder[i]==root->val) {
                rootIndex = i;
                break;
            }
        }
        if(rootIndex==-1) return NULL;
        int leftTreeSize = rootIndex - s1;
        int rightTreeSize = e1 - rootIndex;
        
        root->left = buildBT(inorder, postorder, s1, rootIndex-1, s2, s2+leftTreeSize-1);
        root->right = buildBT(inorder, postorder, rootIndex+1, e1, e2-rightTreeSize, e2-1);
        return root;
    }
};

[LeetCode] Construct Binary Tree from Preorder and Inorder Traversal

Given preorder and inorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

思路：

Binary tree一共3种访问顺序：preorder, inorder, postorder。这道题目的推广就是给定一个binary tree的两种访问顺序，重构该binary tree。这类题目给定的两个排序中，如果包括了inorder，且没有重复元素，就非常好解了。解这类题有两个关键点：

1. 在inorder中寻找root的位置，从而从序列中分割出左右子树。

Inorder: left subtree | root | right subtree

Preorder: root | left subtree | right subtree

Postorder: left subtree | right subtree | root

可见root是preorder序列的第一个节点，也是postorder的最后一个节点。所以给定这两个序列的任意一个我们即知道了root->val。通过搜索inorder序列，可以定位root所在的位置，从而也得到了left subtree和right subtree的节点数。

2. 递归构建

当root，left/right subtree都确定后

root->left = construct(inorder(left subtree), preorder(left subtree))

root->right = construct(inorder(right subtree), preorder(right subtree))

class Solution {
public:
    TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
        if(preorder.size()!=inorder.size()) return NULL;
        int n = preorder.size();
        return buildBT(preorder, inorder, 0, n-1, 0, n-1);
    }
    
    TreeNode *buildBT(vector<int> &preorder, vector<int> &inorder, int s1, int e1, int s2, int e2) {
        if(s1>e1 || s2>e2) return NULL;
        TreeNode *root = new TreeNode(preorder[s1]);
        
        int rootIndex = -1; // root index in inorder
        for(int i=s2; i<=e2; i++) {
            if(inorder[i]==root->val) {
                rootIndex = i;
            }
        }
        if(rootIndex==-1) return NULL;
        int leftTreeSize = rootIndex - s2;
        int rightTreeSize = e2 - rootIndex;
        
        root->left = buildBT(preorder, inorder, s1+1, s1+leftTreeSize, s2, rootIndex-1);
        root->right = buildBT(preorder, inorder, e1-rightTreeSize+1, e1, rootIndex+1, e2);
        return root;
    }
};

[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},

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的值。

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},

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},

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的迭代解法

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的迭代解法

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。

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());