leetcode Populating Next Right Pointers in Each Node(*)

1765 단어 LeetCode
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

관찰 변통 능력을 고찰하고 예를 들면 다음과 같다. 1에 대해 말하자면 1->left->next=1->right;이때 우리는 2층 2->next=3에 입각하여 2층의 체인표를 훑어보고 4->5->6->7을 훑어보고 3층에 입각하여 아래로 훑어볼 수 있다.
/**
 * Definition for binary tree with next pointer.
 * struct TreeLinkNode {
 *  int val;
 *  TreeLinkNode *left, *right, *next;
 *  TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
 * };
 */
class Solution {
public:
    void connect(TreeLinkNode *root) {
        if(root==NULL)return;
        TreeLinkNode* temp=root;
        if(temp->left)temp->left->next=temp->right;
        while(temp->next&&temp->left){
            temp->right->next=temp->next->left;
            temp=temp->next;
            temp->left->next=temp->right;
        }
        connect(root->left);
    }
};

좋은 웹페이지 즐겨찾기