[leedcode 116] Populating Next Right Pointers in Each Node

2929 단어 right
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.
     * public class TreeLinkNode {
     *     int val;
     *     TreeLinkNode left, right, next;
     *     TreeLinkNode(int x) { val = x; }
     * }
     */
    public class Solution {
        public void connect(TreeLinkNode root) {
            ////1、 next , next ( )
            //2、 5->6, next, next 
            if(root==null) return;
            
            if(root.left!=null){
                root.left.next=root.right;
            }
            if(root.right!=null){
                if(root.next!=null){
                    root.right.next=root.next.left;
                }
            }
            connect(root.left);
            connect(root.right);
        }
    }

    좋은 웹페이지 즐겨찾기