leetcode || 117、Populating Next Right Pointers in Each Node II

problem:
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

Hide Tags
 
Tree Depth-first Search
제목: 지난 문제의 일반판입니다. 나무를 가득 채우지 마세요!B* 트리와 유사한 각 레이어 노드 연결
thinking:
(1) 마지막으로 DFS가 아닌 BFS를 사용합니다.http://blog.csdn.net/hustyangju/article/details/45242365
(2)queue 구조로 각 층의 결점을 저장한다
code:
class Solution {
public:
    void connect(TreeLinkNode *root) {
        if(root==NULL)
            return;
        queue<TreeLinkNode*> queue0;
        queue0.push(root);
        level_visit(queue0);
        return;
    }
protected:
    void level_visit(queue<TreeLinkNode*> queue1)
    {
        if(queue1.empty())
            return;
        queue<TreeLinkNode*> queue2=queue1;
        queue<TreeLinkNode*> queue3;
        TreeLinkNode *tmp=queue1.front();
        queue1.pop();
        tmp->next=NULL;
        while(!queue1.empty())
        {
            TreeLinkNode *tmp2=queue1.front();
            queue1.pop();
            tmp2->next=NULL;
            tmp->next=tmp2;
            tmp=tmp2;
        }
        while(!queue2.empty())
        {
            TreeLinkNode *node=queue2.front();
            queue2.pop();
            if(node->left!=NULL)
                queue3.push(node->left);
            if(node->right!=NULL)
                queue3.push(node->right);  
        }
        level_visit(queue3);
    }

};

좋은 웹페이지 즐겨찾기