二叉樹(shù)深度

    public int TreeDepth(TreeNode root) {
        if(root==null)
            return 0;
        int left=TreeDepth(root.left)+1;
        int right=TreeDepth(root.right)+1;
        return Math.max(left,right);
    }

判斷平衡二叉樹(shù)

一種方法 可以利用求二叉樹(shù)深度秆撮，從根節(jié)點(diǎn)開(kāi)始遞歸他宛。再求左右深度進(jìn)行比較船侧。最后求到葉子節(jié)點(diǎn)。但是會(huì)重復(fù)遍歷厅各。
另外一種方法可以利用后序遍歷思路镜撩。當(dāng)遍歷根結(jié)點(diǎn)時(shí)左右子樹(shù)已經(jīng)進(jìn)行了判斷，不會(huì)有重復(fù)遍歷的情況队塘。

public class Solution {
    private boolean isBalanced=true;
    public boolean IsBalanced_Solution(TreeNode root){
        getDepth(root);
        return isBalanced;
    }
    public int getDepth(TreeNode root){
        if(root==null)
            return 0;
        int left=getDepth(root.left);
        int right=getDepth(root.right);
        if(Math.abs(left-right)>1)
            isBalanced=false;
        return right>left?right+1:left+1;
    }

}

判斷是否是二叉搜索樹(shù)的后序遍歷序列

如數(shù)組{5,7,6,9,11,10,8} 是二叉搜索樹(shù)后序遍歷序列袁梗。發(fā)現(xiàn)根節(jié)點(diǎn)8，576小于8憔古，是8左子樹(shù)遮怜，91110大于8是右子樹(shù)，而6又是左子樹(shù)根節(jié)點(diǎn)鸿市，10是右子樹(shù)根節(jié)點(diǎn)锯梁，發(fā)現(xiàn)是遞歸問(wèn)題
方法：從前往后遍歷，大于根節(jié)點(diǎn)時(shí)焰情，為右子樹(shù)试溯。遍歷右子樹(shù)節(jié)點(diǎn)贤姆，如果右子樹(shù)中有節(jié)點(diǎn)值小于根節(jié)點(diǎn)虫溜，則返回false桩皿。對(duì)左子樹(shù)右子樹(shù)進(jìn)行遞歸判斷。

  public boolean judge(int[] a,int start,int end){
        if(start>=end)
            return true;
        int i=start;
        while(i<end&&a[i]<a[end]){
            i++;
        }
        for(int j=i;j<end;j++){
            if(a[j]<a[end])
                return false;
        }
        return judge(a,start,i-1)&&judge(a,i,end-1);
    }

二叉樹(shù)中和為某一值的路徑

題目描述：輸入一顆二叉樹(shù)和一個(gè)整數(shù)验游，打印出二叉樹(shù)中結(jié)點(diǎn)值的和為輸入整數(shù)的所有路徑充岛。路徑定義為從樹(shù)的根結(jié)點(diǎn)開(kāi)始往下一直到葉結(jié)點(diǎn)所經(jīng)過(guò)的結(jié)點(diǎn)形成一條路徑。
DFS問(wèn)題批狱，可以用棧也可以用list裸准。

    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
        ArrayList<ArrayList<Integer>> all=new ArrayList<ArrayList<Integer>>();
        if(root==null)
           return all;
        Stack<Integer> stack=new Stack<Integer>();
        FindPath(root, target,stack,all);
        return all;
     }
     

     
     void FindPath(TreeNode root,int target,Stack<Integer> stack, ArrayList<ArrayList<Integer>> all){
        if(root==null)
            return;
        if((root.left==null&&root.right==null)&&root.val==target){
                ArrayList<Integer> list=new ArrayList<>();
                for(int i:stack){
                    list.add(new Integer(i));
                }
                list.add(new Integer(root.val));
                all.add(list);
        }else{
            stack.push(new Integer(root.val));
            FindPath(root.left,target-root.val,stack,all);
            FindPath(root.right, target-root.val, stack, all);
            stack.pop();
        }
     }
    

使二叉樹(shù)變?yōu)槠溏R像

類似先序遍歷的方法

    public void mirror(TreeNode node){
        if(node==null)
            return;
        TreeNode n=node.left;
        node.left=node.right;
        node.right=n;
        mirror(node.left);
        mirror(node.right);
    }

判斷二叉樹(shù)是否對(duì)稱

左節(jié)點(diǎn)的右子樹(shù)和右節(jié)點(diǎn)的左子樹(shù)相同 使用遞歸

    boolean isSymmetrical(TreeNode pRoot){
        if(pRoot==null)
            return true;
        return comRoot(pRoot.left,pRoot.right);
    }
    
    boolean comRoot(TreeNode left,TreeNode right){
        if(left==null)
            return right==null;
        if(right==null)
            return false;
        if(left.val!=right.val)
            return false;
        return comRoot(left.right, right.left)&&comRoot(left.left, right.right);
    }

樹(shù)的子結(jié)構(gòu)

輸入兩棵二叉樹(shù)A，B赔硫，判斷B是不是A的子結(jié)構(gòu)炒俱。（ps：我們約定空樹(shù)不是任意一個(gè)樹(shù)的子結(jié)構(gòu)）
第一步：查找與根節(jié)點(diǎn)值一樣的節(jié)點(diǎn)，實(shí)際上是樹(shù)的遍歷∪ㄎ颍可以遞歸實(shí)現(xiàn)砸王。
第二步：判斷樹(shù)A中以R為根節(jié)點(diǎn)的子樹(shù)是不是和樹(shù)B具有相同的結(jié)構(gòu)。如果值不同峦阁，肯定不同谦铃。如果相同，再遞歸判斷各自左右節(jié)點(diǎn)榔昔。終止條件時(shí)到了樹(shù)A或樹(shù)B根節(jié)點(diǎn)驹闰。

public class Solution {
        
     public boolean HasSubtree(TreeNode root1,TreeNode root2) {
           boolean result=false;
           if(root1!=null&&root2!=null){
               if(root1.val==root2.val){
                   result=DoesTree1HaveTree2(root1,root2);
               }
               if(!result)
                   result=HasSubtree(root1.left, root2);
               if(!result)
                   result=HasSubtree(root1.right, root2);
           }
           return result;
        }
     
     public boolean DoesTree1HaveTree2(TreeNode root1,TreeNode root2){
         if(root1==null&&root2!=null)
             return false;
         if(root2==null)
             return true;
         if(root1.val!=root2.val)
             return false;
         return DoesTree1HaveTree2(root1.left, root2.left)&&DoesTree1HaveTree2(root1.right, root2.right);
     }
}

多行打印二叉樹(shù)

    public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> result=new ArrayList<ArrayList<Integer>>();   
        if(pRoot==null)
            return result;
        Queue<TreeNode> layer=new LinkedList<>();
        ArrayList<Integer> list=new ArrayList<Integer>();
       layer.add(pRoot);
       int start=0,end=1;
       while(!layer.isEmpty()){
           TreeNode cur=layer.remove();
           list.add(cur.val);
           start++;
           if(cur.left!=null)
               layer.add(cur.left);
           if(cur.right!=null)
               layer.add(cur.right);
           if(start==end){
               end=layer.size();
               start=0;
               result.add(list);
               list=new ArrayList<>();
           }
       }
       return result;
    }

之字形打印二叉樹(shù)

利用棧后進(jìn)先出的特性，兩個(gè)棧一個(gè)存奇數(shù)層節(jié)點(diǎn)撒会，一個(gè)存偶數(shù)層節(jié)點(diǎn)

    /*
     * 請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)按照之字形打印二叉樹(shù)嘹朗，即第一行按照從左到右的順序打印，
     * 第二層按照從右至左的順序打印诵肛，第三行按照從左到右的順序打印屹培，其他行以此類推。
     */
    //{8,6,10,5,7,9,11}
    public static ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> all=new ArrayList<ArrayList<Integer>>();  
        int layer=1;
        Stack<TreeNode> s1=new Stack<TreeNode>();
        Stack<TreeNode> s2=new Stack<TreeNode>();
        s1.push(pRoot);
        while(!s1.empty()||!s2.empty()){
            if(layer%2!=0){
                ArrayList<Integer> temp=new ArrayList<Integer>();
                while(!s1.empty()){
                    TreeNode node=s1.pop();
                    if(node!=null){
                        temp.add(node.val);
                        System.out.print(node.val + " ");
                        s2.push(node.left);
                        s2.push(node.right);
                    }
                }
                if(!temp.isEmpty()){
                    all.add(temp);
                    layer++;
                    System.out.println();
                }
            }else{
                ArrayList<Integer> temp=new ArrayList<Integer>();
                while(!s2.empty()){
                    TreeNode node=s2.pop();
                    if(node!=null){
                        temp.add(node.val);
                        System.out.print(node.val + " ");
                        s1.push(node.right);
                        s1.push(node.left);
                    }
                }
                if(!temp.isEmpty()){
                    all.add(temp);
                    layer++;
                    System.out.println();
                }
            }
            
        }
        return all;
    }

重構(gòu)二叉樹(shù)

輸入某二叉樹(shù)的前序遍歷和中序遍歷的結(jié)果怔檩，請(qǐng)重建出該二叉樹(shù)褪秀。假設(shè)輸入的前序遍歷和中序遍歷的結(jié)果中都不含重復(fù)的數(shù)字。例如輸入前序遍歷序列{1,2,4,7,3,5,6,8}和中序遍歷序列{4,7,2,1,5,3,8,6}薛训，則重建二叉樹(shù)并返回媒吗。

    public TreeNode reConstructBinaryTree(int[] pre,int[] in){
        if(pre.length==0||in.length==0)
            return null;
        TreeNode node=new TreeNode(pre[0]);
        for(int i=0;i<in.length;i++){
            if(pre[0]==in[i]){
                node.left=reConstructBinaryTree(Arrays.copyOfRange(pre, 1, i+1),Arrays.copyOfRange(in, 0, i));
                node.right=reConstructBinaryTree(Arrays.copyOfRange(pre, i+1, pre.length), Arrays.copyOfRange(in, i+1, in.length));
            }
        }
        return node;
    }

二叉搜索樹(shù)的第k個(gè)節(jié)點(diǎn)

給定一顆二叉搜索樹(shù)，請(qǐng)找出其中的第k大的結(jié)點(diǎn)许蓖。例如蝴猪， 5 / \ 3 7 /\ /\ 2 4 6 8 中，按結(jié)點(diǎn)數(shù)值大小順序第三個(gè)結(jié)點(diǎn)的值為4膊爪。

public class Solution {
    int index=0;
    TreeNode KthNode(TreeNode root, int k)
    {
        if(root!=null){
            TreeNode node=KthNode(root.left,k);
            if(node!=null)
                return node;
            index++;
            if(index==k)
                return root;
            node=KthNode(root.right,k);
            if(node!=null)
                return node;
        }
        return null;
    }  
}