Binary Tree Right Side View

Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.
For example:
Given the following binary tree,

   1            <---
 /   \
2     3         <---
 \     \
  5     4       <---

You should return [1, 3, 4].


Naive Way: Use a level-order traversal and always note down the last TreeNode value in the result.

 /**  
  * Definition for binary tree  
  * public class TreeNode {  
  *   int val;  
  *   TreeNode left;  
  *   TreeNode right;  
  *   TreeNode(int x) { val = x; }  
  * }  
  */  
 public class Solution {  
   public List<Integer> rightSideView(TreeNode root) {  
     List<Integer> list = new ArrayList<Integer>();  
     List<TreeNode> cur_layer = new ArrayList<TreeNode>();  
     // edge case  
     if(root==null) return list;  
     // initialize current layer  
     cur_layer.add(root);  
     // level-order traversal  
     while(!cur_layer.isEmpty()){  
       list.add(cur_layer.get(cur_layer.size()-1).val);  
       List<TreeNode> next_layer = new ArrayList<TreeNode>();  
       for(TreeNode node: cur_layer){  
         if(node.left!=null) next_layer.add(node.left);  
         if(node.right!=null) next_layer.add(node.right);  
       }  
       cur_layer = next_layer;  
     }  
     return list;  
   }  
 }  

Same Tree

Given two binary trees, write a function to check if they are equal or not.
Two binary trees are considered equal if they are structurally identical and the nodes have the same value.

Naive Way: The question is not difficult. Write both iterative and recursive methods.

Recursive Method.

 /**  
  * Definition for binary tree  
  * public class TreeNode {  
  *   int val;  
  *   TreeNode left;  
  *   TreeNode right;  
  *   TreeNode(int x) { val = x; }  
  * }  
  */  
 public class Solution {  
   public boolean isSameTree(TreeNode p, TreeNode q) {  
     // base case  
     if(p==null || q==null) return p==null && q==null;  
     // recursion  
     return p.val==q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);  
   }  
 }  

Iterative Method.

 /**  
  * Definition for binary tree  
  * public class TreeNode {  
  *   int val;  
  *   TreeNode left;  
  *   TreeNode right;  
  *   TreeNode(int x) { val = x; }  
  * }  
  */  
 public class Solution {  
   public boolean isSameTree(TreeNode p, TreeNode q) {  
     // edge case  
     if(p==null || q==null) return p==null && q==null;  
     // general case, BFS  
     Queue<TreeNode> p_queue = new LinkedList<TreeNode>();  
     Queue<TreeNode> q_queue = new LinkedList<TreeNode>();  
     p_queue.offer(p);  
     q_queue.offer(q);  
     while(!p_queue.isEmpty() && !q_queue.isEmpty()){  
       TreeNode p_node = p_queue.poll();  
       TreeNode q_node = q_queue.poll();  
       if(p_node.val!=q_node.val) return false;  
       if(p_node.left!= null && q_node.left!=null){  
         p_queue.offer(p_node.left);  
         q_queue.offer(q_node.left);  
       }else if(!(p_node.left==null && q_node.left==null))  
         return false;  
       if(p_node.right!= null && q_node.right!=null){  
         p_queue.offer(p_node.right);  
         q_queue.offer(q_node.right);  
       }else if(!(p_node.right==null && q_node.right==null))  
         return false;  
     }  
     return p_queue.isEmpty() && q_queue.isEmpty();  
   }  
 }  

Balanced Binary Tree

Given a binary tree, determine if it is height-balanced.
For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Naive Way: 一开始想到的还是一个recursive的方法，求出两边的height，然后一旦有不符合的就返回false。

算法复杂度O(n), space O(n)。

 /**  
  * Definition for binary tree  
  * public class TreeNode {  
  *   int val;  
  *   TreeNode left;  
  *   TreeNode right;  
  *   TreeNode(int x) { val = x; }  
  * }  
  */  
 public class Solution {  
   boolean balanced;  
   public boolean isBalanced(TreeNode root) {  
     balanced = true;  
     heightOf(root);  
     return balanced;  
   }  
   private int heightOf(TreeNode root){  
     if(root==null) return 0;  
     int left = heightOf(root.left), right = heightOf(root.right);  
     if(Math.abs(left-right) > 1) balanced = false;  
     return Math.max(left,right)+1;  
   }  
 }  

以上做法是一个postorder traversal 的做法，所以应该可以写成对应的iterative的形式。

算法复杂度O(n), space O(n)。

 public class Solution {  
   public boolean isBalanced(TreeNode root) {  
     if(root==null) return true;  
     Stack<TreeNode> stack = new Stack<TreeNode>();  
     Map<TreeNode, Integer> map = new HashMap<TreeNode, Integer>();  
     stack.push(root);  
     while(!stack.isEmpty()){  
       TreeNode node = stack.pop();  
       if((node.left==null || node.left!=null && map.containsKey(node.left)) &&(node.right==null || node.right!=null && map.containsKey(node.right))){  
         int left = node.left==null?0:map.get(node.left);  
         int right = node.right==null?0:map.get(node.right);  
         if(Math.abs(left-right) > 1) return false;  
         map.put(node, Math.max(left, right)+1);  
       }else{  
         if(node.left!=null && !map.containsKey(node.left)){  
           stack.push(node);  
           stack.push(node.left);  
         }else{  
           stack.push(node);  
           stack.push(node.right);  
         }  
       }  
     }  
     return true;  
   }  
 }  

Improved Way: 看到一个人用return -1来消去全局变量的做法，实在高明。
来自 pavel-shlyk

 public boolean isBalanced(TreeNode root) {  
   return root == null || balance(root, 1) > 0;  
 }  
 private int balance(TreeNode node, int level) {  
   int l = node.left != null ? balance(node.left, level+1) : level;  
   int r = node.right != null ? balance(node.right, level+1) : level;  
   if (l == -1 || r == -1 || Math.abs(r - l) > 1) return -1;  
   return Math.max(l, r);  
 }  

Binary Tree Maximum Path Sum

Binary Tree Maximum Path Sum

 

Given a binary tree, find the maximum path sum.
The path may start and end at any node in the tree.
For example:
Given the below binary tree,

       1
      / \
     2   3

Return 6.


Naive Way: 可以用一个recursive的方法，不断比较sum(root.left), sum(root.right)和root.val，在回溯过程中遇到正数也要和最大值比较。

 

Recursive的方法，算法复杂度O(n), space O(n)。这里因为Integer.MIN_VALUE+负数 =正数,所以不能直接写return max(root.val, root.val+right, root.val+left)，必须确认left.val和right.val都是正数。

 

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    int max = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        int rootSum = pSum(root);
        return Math.max(rootSum,max);
    }
    
    private int pSum(TreeNode root) {
        // base case
        if(root==null){return Integer.MIN_VALUE;}
        // recursive
        int left = pSum(root.left);
        int right = pSum(root.right);
        max = Math.max(left,max);
        max = Math.max(right,max);
        if(left < 0 && right < 0)
            return root.val;
        else if(left < 0)
            return root.val+right;
        else if(right < 0)
            return root.val+left;
        else
            max = Math.max(root.val+left+right,max);
        return root.val + Math.max(right,left);
    }
    
}

下面是iterative的方法。使用了level-order traversal，相当于BFS，正着一遍将所有节点放入对应的层中，然后倒着一遍由下往上求一遍。还可以用DFS遍历一遍然后全存入一个堆栈中，遍历完后再逐个推出堆栈，因为其顺序也是倒着的（相当于拓扑排序的顺序）。

public class Solution {
    public int maxPathSum(TreeNode root) {
        // level-order traversal
        List<List<TreeNode>> gross = new ArrayList<List<TreeNode>>();
        int max = Integer.MIN_VALUE;
        // initialize
        List<TreeNode> first_layer = new ArrayList<TreeNode>();
        if(root!=null) first_layer.add(root);
        gross.add(first_layer);
        while(gross.get(gross.size()-1).size() > 0){
            List<TreeNode> new_layer = new ArrayList<TreeNode>();
            List<TreeNode> pre_layer = gross.get(gross.size()-1);
            for(int i = 0;i < pre_layer.size();i++){
                TreeNode node = pre_layer.get(i);
                if(node.left!=null) new_layer.add(node.left);
                if(node.right!=null) new_layer.add(node.right);
            }
            gross.add(new_layer);
        }
        
        // back trace
        int index = gross.size();
        while(--index >= 0){
            List<TreeNode> last_layer = gross.get(index);
            for(int i = 0;i < last_layer.size();i++){
                TreeNode node = last_layer.get(i);
                if(node.right!=null && node.left==null){
                    node.val += node.right.val>0?node.right.val:0;
                }else if(node.left!=null && node.right==null){
                    node.val += node.left.val>0?node.left.val:0;
                }else if(node.left!=null && node.right!=null){
                    max = Math.max(max, node.val+node.left.val+node.right.val);
                    node.val += Math.max(Math.max(node.left.val,node.right.val),0);
                }
                max = Math.max(max,node.val);
            }
        }
        
        return max;
    }
}

Symmetric Tree

Symmetric Tree

 

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).
For example, this binary tree is symmetric:

    1
   / \
  2   2
 / \ / \
3  4 4  3

But the following is not:

    1
   / \
  2   2
   \   \
   3    3

Note:
Bonus points if you could solve it both recursively and iteratively.


Naive Way: 要求用recursive和iterative两种方法。iterative的方法可以是分别对左右子树进行DFS，一个先enqueue左节点，一个先enqueue右节点，不相等则返回。recursive的方法，因为根的两边为镜像时，左右子节点做根的时候其子树并不镜像，有点不好写。我想到了用preorder traversal和postorder traversal分别遍历得到list,比较是否一致。后来发现这两者并不是镜像（这两者肯定不是镜像的啊），于是改成比较 左-右-中  和  右-左-中 的遍历，看得到的序列是否一致。

这是我写的iterative的做法，算法复杂度O(n), space O(n)。

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean isSymmetric(TreeNode root) {
        Stack<TreeNode> left = new Stack<TreeNode>();
        Stack<TreeNode> right = new Stack<TreeNode>();
        if(root==null){return true;}
        if(root.left!=null)
            left.push(root.left);
        if(root.right!=null)
            right.push(root.right);
        while(!left.isEmpty() && !right.isEmpty()){
            TreeNode leftNode = left.pop();
            TreeNode rightNode = right.pop();
            // mirror push
            if(leftNode.val!=rightNode.val){return false;}
            if(leftNode.left!=null && rightNode.right!=null){
                left.push(leftNode.left);
                right.push(rightNode.right);
            }else{
                if(!(leftNode.left==null && rightNode.right==null))
                    return false;
            }
            if(leftNode.right!=null && rightNode.left!=null){
                left.push(leftNode.right);
                right.push(rightNode.left);
            }else{
                if(!(leftNode.right==null && rightNode.left==null))
                    return false;
            }
        }
        return left.size()==right.size();
    }
}

这是我写的recursive的做法，算法复杂度O(n), space O(n)。 当左子结点或者右子节点为空时，也必须加入list中，否则会因为轮空位置不同，不镜像的树得到相同结果。

public class Solution {
    public boolean isSymmetric(TreeNode root) {
        List<TreeNode> preorder = new ArrayList<TreeNode>();
        List<TreeNode> postorder = new ArrayList<TreeNode>();
        traversal_preorder(root, preorder);
        traversal_postorder(root, postorder);
        for(int i = 0;i < preorder.size() && i < postorder.size();i++){
            if(preorder.get(i)==null && postorder.get(i)==null)
                continue;
            if(preorder.get(i)==null || postorder.get(i)==null)
                return false;
            if(preorder.get(i).val!=postorder.get(i).val)
                return false;
        }
        return preorder.size()==postorder.size();
    }
    
    private void traversal_preorder(TreeNode root, List<TreeNode> list){
        if(root==null){return;}
        if(root.left==null)
            list.add(null);
        else
            traversal_preorder(root.left,list);
        
        if(root.right==null)
            list.add(null);
        else
            traversal_preorder(root.right,list);
        list.add(root);
    }
    
    private void traversal_postorder(TreeNode root, List<TreeNode> list){
        if(root==null){return;}
        if(root.right==null)
            list.add(null);
        else
            traversal_postorder(root.right,list);
        
        if(root.left==null)
            list.add(null);
        else
            traversal_postorder(root.left,list);
        list.add(root);
    }
}

Improved Way:显然我的这个recursive不是一个好的recursive，它实际上是一种作弊，因为不能仅通过recursive得到boolean值。后来看到了别人传递两个参数的recursive函数，茅塞顿开。

这个方法具有一般recursive的特点，就是简短，算法复杂度是O(n), space O(n)。

public class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root==null){return true;}
        return isSymmetric(root.left, root.right);
    }
    
    private boolean isSymmetric(TreeNode a, TreeNode b){
        if(a==null&&b==null){return true;}
        if(a==null||b==null){return false;}
        if(a.val!=b.val){return false;}
        return isSymmetric(a.left,b.right)&&isSymmetric(a.right,b.left);
    }
}

Binary Tree Level Order Traversal II

Binary Tree Level Order Traversal II

 

Given a binary tree, return the bottom-up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root).
For example:
Given binary tree {3,9,20,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

return its bottom-up level order traversal as:

[
  [15,7],
  [9,20],
  [3]
] 

Naive Way: 这题，不就是之前那题把list的顺序倒过来吗。然后用了一个stack倒转顺序。

/**

 * Definition for binary tree

 * public class TreeNode {

 *     int val;

 *     TreeNode left;

 *     TreeNode right;

 *     TreeNode(int x) { val = x; }

 * }

 */

public class Solution {

    public List<List<Integer>> levelOrderBottom(TreeNode root) {

        List<List<Integer>> rlst = new ArrayList<List<Integer>>();

        Stack<List<Integer>> stack = new Stack<List<Integer>>();

        Map<TreeNode, Integer> map = new HashMap<TreeNode, Integer>();

        Queue<TreeNode> queue = new LinkedList<TreeNode>();

        if(root==null){return rlst;}

        queue.add(root);

        map.put(root,0);

        while(!queue.isEmpty()){

            TreeNode node = queue.poll();

            int layer = map.get(node);

            List<Integer> list;

            if(rlst.size() > layer){

                list = rlst.get(layer);

            }else{

                list = new ArrayList<Integer>();

                rlst.add(list);

            }

            rlst.get(layer).add(node.val);

            if(node.left!=null){

                queue.add(node.left);

                map.put(node.left, layer+1);

            }

            if(node.right!=null){

                queue.add(node.right);

                map.put(node.right, layer+1);

            }

        }

        for(int i = 0;i < rlst.size();i++)

            stack.push(rlst.get(i));

        rlst.clear();

        while(!stack.isEmpty()){

            rlst.add(stack.pop());

        }

        return rlst;

    }

} 

Improved Way:能否直接得到倒转的list而不是得到正的再颠倒它呢。

 

Binary Tree Level Order Traversal

Binary Tree Level Order Traversal

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).
For example:
Given binary tree {3,9,20,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

return its level order traversal as:

[
  [3],
  [9,20],
  [15,7]
] 

Naive Way: 一看就觉得这不是BFS吗。用以前的做法，用queue进行BFS遍历，用一个Map存节点对应的层数。

不知道是不是应该有更好的做法。

/**

 * Definition for binary tree

 * public class TreeNode {

 *     int val;

 *     TreeNode left;

 *     TreeNode right;

 *     TreeNode(int x) { val = x; }

 * }

 */

public class Solution {

    public List<List<Integer>> levelOrder(TreeNode root) {

        List<List<Integer>> rlst = new ArrayList<List<Integer>>();

        Map<TreeNode, Integer> map = new HashMap<TreeNode, Integer>();

        Queue<TreeNode> queue = new LinkedList<TreeNode>();

        if(root==null){return rlst;}

        queue.add(root);

        map.put(root,0);

        while(!queue.isEmpty()){

            TreeNode node = queue.poll();

            int layer = map.get(node);

            List<Integer> list;

            if(rlst.size() > layer){

                list = rlst.get(layer);

            }else{

                list = new ArrayList<Integer>();

                rlst.add(list);

            }

            rlst.get(layer).add(node.val);

            if(node.left!=null){

                queue.add(node.left);

                map.put(node.left, layer+1);

            }

            if(node.right!=null){

                queue.add(node.right);

                map.put(node.right, layer+1);

            }

        }

        return rlst;

    }

}

Populating Next Right Pointers in Each Node

Populating Next Right Pointers in Each Node

 

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 

Naive Way: 这里有一个重要限制是constant space.所以不能用stack或者queue来进行遍历。

这里有个问题困扰了我，如何在不用extra space的前提下遍历一颗无父指针二叉树呢。答案是不可能的！

因为二叉树有两个分支，无论先遍历哪一边分支，都必须要记下兄弟节点，否则一旦往下走就不能回头。

而且光记录一个兄弟节点还不行，必须把同一层的兄弟节点都记录下来，这样是和BFS，DFS相对应的O(n)

space。

明白这一点很重要，说明这道题在坑人。

终于过了好久，我发现这道题的next指针导致了我们可以用constant space去遍历一整棵树。 

因为如果我们知道next指针，就可以通过父节点的next指针访问到同一层的兄弟节点。也就是说，

我们不仅要连起这些next指针，还要利用之前连好的这些next指针方便我们连下一层的next指针。

简单的逻辑描述为：

如果一个节点为左节点，其next为父亲的右节点。

如果一个节点为右节点，其next为父亲节点的next节点的左节点（如果有的话）。

并且由于next指针是从左指向右的，我觉得应该从左往右进行遍历。通过next获得下一个要

处理的节点。

写点有点别扭，用了一个do-while语句。但是思想应该是对的。一层一层来，从左到右，

每一层都要记下最左边的子节点，作为下一层遍历的开头。

/**

 * 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) {
        if(root==null)
            return;
        TreeLinkNode leftMost = root;
        TreeLinkNode node = null;
        while(leftMost.right!=null && leftMost.left!=null){
            node = leftMost;
            leftMost = node.left;
            do{
                node.left.next = node.right;
                node.right.next = node.next==null?null:node.next.left;
                node = node.next;
            }while(node!=null);
        }
    }
}

 

Populating Next Right Pointers in Each Node II

Populating Next Right Pointers in Each Node II

 

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 

Naive Way:这次多了一个不满秩的条件，很明显的意图是要看能否通过修改第一次的代码得到。

第一次的代码：

public void connect(TreeLinkNode root) {
        if(root==null)
            return;
        TreeLinkNode leftMost = root;
        TreeLinkNode node = null;
        while(leftMost.right!=null && leftMost.left!=null){
            node = leftMost;
            leftMost = node.left;
            do{
                node.left.next = node.right;
                node.right.next = node.next==null?null:node.next.left;
                node = node.next;
            }while(node!=null);
        }
    }

我想基本结构应该是不变，但是现在左子节点和右子节点都可能不存在。分析一下不存在的时候该怎么办：

1.如果左子节点不存在，最左边的节点就应该是右节点。

2.如果右子节点不存在，next该指向的是父节点的next节点的左子节点。

很棒，这两点是相互作用的.对于找最左子节点和右节点分别写了对应函数，发现二者仅一处不同。

private TreeLinkNode searchLeft(TreeLinkNode node){
        if(node==null)
            return null;
        if(node.left!=null)
            return node.left;
        if(node.right!=null)
            return node.right;
        return searchLeft(node.next);
    }

private TreeLinkNode searchRight(TreeLinkNode node){
        if(node==null)
            return null;
        if(node.right!=null)
            return node.right;
        return searchLeft(node.next);
    }

替换相应部分的结果为：

（这里结束条件需要略作改动，因为不能再用是否满秩作为判断条件。后来想想，应该第一个也这样写的） 

public void connect(TreeLinkNode root) {

       if(root==null)

           return;

       TreeLinkNode leftMost = root;

       TreeLinkNode node = null;

       while(leftMost!=null){

           node = leftMost;

           leftMost = searchLeft(node);

           do{
              if(node.left!=null)

                   node.left.next = searchRight(node);

               if(node.right!=null)

                   node.right.next = searchLeft(node.next);

               node = node.next;

           }while(node!=null);

       }

   } 

Improved Way: 这样是否就已经可以了呢。我在discuss中看到一个很有意思的想法。有个人先把搜友节点的next节点指向父节点，然后展开BFS把next pointer指向下一个。感觉和我的思路是一样的，都是要先把上一层的next连好，记下下一层最左边的，然后通过上一层的next找同层的兄弟节点。但是把next指向父节点就有了无限可能性，因为可以no extra space从下往上遍历节点了。

以下代码是leetcode用户 pavan.singitham的。

public class Solution {
public void connect(TreeLinkNode root) {
    if(root == null) {
        return;
    }
    root.next = null;
    pointChildrenToParents(root);
    rotateNextClockwise(root);
}

// point each child's next pointer to the parent
private void pointChildrenToParents(TreeLinkNode root) {
    if(root == null) {
        return;
    }
    if(root.left != null) {
        root.left.next = root;
        pointChildrenToParents(root.left);
    }
    if(root.right != null) {
        root.right.next = root;
        pointChildrenToParents(root.right);
    }
}

// now update the next pointer 1-level at a time to point to the next node in that level
private void rotateNextClockwise(TreeLinkNode root) {
    if(root == null) {
        return;
    }

    TreeLinkNode firstNodeInNextLevel = null; // save first node in next level for bfs
    while(root != null) {
        if(firstNodeInNextLevel == null) {
            firstNodeInNextLevel = (root.left != null)? root.left : root.right;
        }
        if(root.right != null) {
            if(root.left != null) {
                root.left.next = root.right;
            }
            root.right.next = findNextChild(root.next);
            root = (root.right.next != null) ? root.right.next.next: null;
        }
        else if(root.left != null) {
            root.left.next = findNextChild(root.next);
            root = (root.left.next != null) ? root.left.next.next: null;
        }
        else {
            root = root.next;
        }
    }

    rotateNextClockwise(firstNodeInNextLevel);
}

// traverse next chain till we find a child for current level
private TreeLinkNode findNextChild(TreeLinkNode root) {
    for(TreeLinkNode tmp = root; tmp != null; tmp = tmp.next) {
        if(tmp.left != null) {
            return tmp.left;
        }
        else if(tmp.right != null) {
            return tmp.right;
        }
    }
    return null;
} 

} 

看到一个更好的代码，思路是一样的，带式代码质量好很多。来自leetcode的 davidtan1890用户。

public void connect(TreeLinkNode root) {

        while(root != null){
            TreeLinkNode tempChild = new TreeLinkNode(0);
            TreeLinkNode currentChild = tempChild;
            while(root!=null){
                if(root.left != null) { currentChild.next = root.left; currentChild = currentChild.next;}
                if(root.right != null) { currentChild.next = root.right; currentChild = currentChild.next;}
                root = root.next;
            }
            root = tempChild.next;
        }
    }