过程题 -- 弄清楚怎么链接

116. Populating Next Right Pointers in Each Node

指针操作题 观察得到相应的链接规律 更为普遍的情况参加下面的117

117. Populating Next Right Pointers in Each Node II

Core: Level Order Traversal. The difference is we don't need a Queue here because all requires is a pointer to the start of each levels. We keep a pre pointer to represent and connect nodes in each level. And we keep the last upper levels head pointer and the current level's head pointer in case we needed.

指针链接题 注意不要改变原来的结构 ~

public class Solution {
    public void connect(TreeLinkNode root) {
        if(root == null)return;
        //每一层用来移动的指针
        TreeLinkNode pre = null;
        //Upper level's first head and current level's first head 
        TreeLinkNode lastHead = root;
        TreeLinkNode curHead = null;
        while(lastHead!=null){
            //move forward the pointer forward and connected each other
            TreeLinkNode lastCur = lastHead;
            while(lastCur!= null){
                if(lastCur.left!=null){
                    if(curHead == null){
                        curHead = lastCur.left;
                        pre = curHead;
                    }
                    else{
                        pre.next = lastCur.left;
                        pre = pre.next;
                    }
                }
                if(lastCur.right!=null){
                    if(curHead == null){
                        curHead = lastCur.right;
                        pre = curHead;
                    }
                    else{
                        pre.next = lastCur.right;
                        pre = pre.next;
                    }
                }
            }
            lastHead = curHead;
            curHead = null;
        }
    }
}

LinkedList优势 快速remove

272. Closest Binary Search Tree Value II

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 * Inorder traverse get the sorted array and push into the res list if necessary
 * Remove element if the size is not enough 
 */
public class Solution {
    public List<Integer> closestKValues(TreeNode root, double target, int k) {
         List<Integer> res = new LinkedList<>();
         InorderTraverse(root,target,k,res);
         return res;
    }
    public void InorderTraverse(TreeNode root,double target,int k,List<Integer> list){
        if(root == null)return;
        InorderTraverse(root.left,target,k,list);
        if(list.size() < k){
            list.add(root.val);
        }
        else if(list.size() == k){
            //如果起始值与target的value的差值比当前的大则去除list的开头并且在尾部加入当前点
            if(Math.abs(list.get(0) - target) > Math.abs(root.val - target)){
                list.remove(0);
                list.add(root.val);
            }
            else{
                return;
            }
        }
        InorderTraverse(root.right,target,k,list);
    }
}