[LeetCode72]Populating Next Right Pointers in Each Node

1639 단어 LeetCodetreebinary
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

Analysis:
현재 층이next 바늘의 연결을 처리한 후에 다음 노드를 호출합니다.
Java
public void connect(TreeLinkNode root) {
       if(root == null) return;
		if(root.left!=null) root.left.next = root.right;
		if(root.right!=null)
			root.right.next = (root.next) != null ? root.next.left:null;
		connect(root.left);
		connect(root.right); 
    }

c++
void connect(TreeLinkNode *root) {
     if(root == NULL) return;
     if(root->left != NULL)
        root->left->next = root->right;
     if(root->right != NULL)
        root->right->next = root->next ? root->next->left:NULL;
     connect(root->left);
     connect(root->right);
}

좋은 웹페이지 즐겨찾기