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 7After calling your function, the tree should look like:
1 -> NULL / / 2 -> 3 -> NULL / / / /4->5->6->7 -> NULLs思路： 1. 还是树。变化是：除了纵向的遍历树，现在还要增加功能，使其可以横向遍历。 2. 初略观察有两种pattern：一种是，2的next指向就是2的parent的child 3;另一种，5的next是5的parent的next 3的child。或者不一定这么看，问题的另一面是：2的左孩子的next是2的右孩子；2的右孩子的next是2的next的左孩子。也是两种情况，不同的是，一种从下往上看，所以每个node都借助parent;一种是从上往下看，所以每个node都借组child。由于是树，找孩子容易，找父母难。自然我们选择用第二个思路，不过两个思路都是一个思路的两个角度。 3. 上面的思路也就意味着
//方法1： recursive.先处理root,然后左，最后右。in-orderclass Solution {public: void connect(TreeLinkNode *root) { // if(!root) return; if(!root->left&&!root->right) return; root->left->next=root->right; if(root->next) root->right->next=root->next->left; connect(root->left); connect(root->right); }};//方法2： iterative.不用queue,也不用stack.单用双重循环就够了，一个从上往下，一个从左往右class Solution {public: void connect(TreeLinkNode *root) { // TreeLinkNode* horizon=NULL,*vertical=root; while(vertical&&vertical->left){ horizon=vertical; while(horizon){ if(horizon->left) horizon->left->next=horizon->right; if(horizon->next) horizon->right->next=horizon->next->left; horizon=horizon->next; } vertical=vertical->left; } }};新闻热点
疑难解答
