目标：每日更新。还有两个月。过一遍！！

2017-5-20 topic：树

5.24更新

4.1 二叉树平衡检查

题目描述
实现一个函数，检查二叉树是否平衡，平衡的定义如下，对于树中的任意一个结点，其两颗子树的高度差不超过1。
给定指向树根结点的指针TreeNode* root，请返回一个bool，代表这棵树是否平衡。

import java.util.*;

/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    public TreeNode(int val) {
        this.val = val;
    }
}*/
public class Balance {
    public boolean isBalance(TreeNode root) {
        if(root==null) return true;
        // write code here
        if(Math.abs(length(root.left)-length(root.right))>1)
            return false;
        else
            return isBalance(root.left)&&isBalance(root.right);
    }
    
    public int length(TreeNode root){ 
        if(root==null)
            return 0;
        else{
            return Math.max(length(root.left), length(root.right))+1;
        }
    }
}

总结 ：上述代码 会重复计算某个节点的高度，复杂度是nlogn。

题目描述

对于一个元素各不相同且按升序排列的有序序列，请编写一个算法，创建一棵高度最小的二叉查找树

//根据一个有序升序的数组，创建一个最小高度的二叉搜索树
    Node createMinBST(int arr[] ,int start ,int end){
        int l=start;
        int r=end;
        int middle=(l+r)/2;
        Node node= new Node(arr[middle],null,null);
        node.leftNode=createMinBST(arr, l, middle-1);
        node.rightNode=createMinBST(arr, middle+1, r);      
        return node;                
    }
    Node createMinBST(int arr[]){
        return createMinBST(arr, 0, arr.length-1);
    }
    
    int getLength(Node root){
        if(root==null) return 0;
        return Math.max(getLength(root.leftNode), root.rightNode)+1;
        
    }

备注 ：如果求高度的话，可以先构建 ，再求高度，不过这样子会运算两次。

题目描述

对于一棵二叉树，请设计一个算法，创建含有某一深度上所有结点的链表。

给定二叉树的根结点指针TreeNode* root，以及链表上结点的深度，请返回一个链表ListNode，代表该深度上所有结点的值，请按树上从左往右的顺序链接，保证深度不超过树的高度，树上结点的值为非负整数且不超过100000。

第一印象，想到了层次遍历。又想到了s型打印。在层次遍历(因为要打印一层，用两个queue)的基础上记录下，每次到第几层了。最后打印一下。创建一个链表。

    //打印某一深度上的所有节点。
    
    void getNodeByDep(Node root,int dep){
        LinkedList<Node> list1= new LinkedList<>();
        LinkedList<Node> list2= new LinkedList<>();
        if (root==null) return;
        int tmp=1;
        list1.add(root);
        while(tmp<=dep-1 &&!list1.isEmpty()){
            while(!list1.isEmpty()){
                Node node=list1.poll();
                if(node.leftNode!=null){
                    list2.add(node.leftNode);
                }
                if(node.rightNode!=null){
                    list2.add(node.rightNode);
                }
            }
            LinkedList<Node> tp=list1;
            list1=list2;        
            list2=tp;
            tmp++;
        }
        if(tmp==dep)
            for(Node node:list1)
                System.out.print(node.value+" ");
        else
            System.out.print("none");   
    }