【Leetcode】Populating Next Right Pointers in Each Node

1926 단어
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

분석: 트리 처리에 가장 많이 사용되는 것은 반복과 귀속 알고리즘이기 때문에 고려할 때 가능한 한 이 방면에 의지할 수 있다.
차례차례 좌우 나무를 그의 오른쪽 바늘과 연결시켰다
/**
 * 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;
            
        connectToright(root, NULL);
        
    }
    
private:

    void connectToright(TreeLinkNode *node, TreeLinkNode *sibling) {
        if(node == NULL)
            return;
            
        node->next = sibling;
        
        if(node->left && node->right)
            connectToright(node->left, node->right);
        
        if(sibling != NULL)
        {
            connectToright(node->right, sibling->left);
        }
        else
            connectToright(node->right, NULL);
    }

};

좋은 웹페이지 즐겨찾기