[数据结构与算法]二叉树递归套路(树形DP)

二叉树的直径

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public class Info{
        public int height;
        public int maxPath;
        public Info(int a,int b){
            height=a;
            maxPath=b;
        }
    }
    public Info process(TreeNode x){
        if(x==null)return null;
        Info leftInfo=process(x.left);
        Info rightInfo=process(x.right);
        int height=0,maxPath=0;
        height=Math.max((leftInfo==null?0:leftInfo.height),(rightInfo==null?0:rightInfo.height))+1;
        maxPath=(leftInfo==null?0:leftInfo.height)+(rightInfo==null?0:rightInfo.height);
        maxPath=Math.max(maxPath,Math.max((leftInfo==null?0:leftInfo.maxPath),(rightInfo==null?0:rightInfo.maxPath)));
        return new Info(height,maxPath);
    }
    public int diameterOfBinaryTree(TreeNode root) {
        return process(root).maxPath;
    }
}

二叉树的坡度

二叉搜索树的最近公共祖先

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public class Info{
        public boolean isFindP;
        public boolean isFindQ;
        public TreeNode ancestor;
        public Info(boolean a,boolean b,TreeNode c){
            isFindP=a;
            isFindQ=b;
            ancestor=c;
        }
    }
    public Info process(TreeNode x,TreeNode p,TreeNode q){
        if(x==null){
            return null;
        }
        Info leftInfo=process(x.left,p,q);
        Info rightInfo=process(x.right,p,q);
        boolean isFindP=false;
        boolean isFindQ=false;
        TreeNode ancestor=null;
        isFindP=(leftInfo==null?false:leftInfo.isFindP)|(rightInfo==null?false:rightInfo.isFindP)|(x==p);
        isFindQ=(leftInfo==null?false:leftInfo.isFindQ)|(rightInfo==null?false:rightInfo.isFindQ)|(x==q);
        if(leftInfo!=null&&leftInfo.isFindP&&leftInfo.isFindQ){
            ancestor=leftInfo.ancestor;
        }
        if(rightInfo!=null&&rightInfo.isFindP&&rightInfo.isFindQ){
            ancestor=rightInfo.ancestor;
        }
        if(leftInfo!=null&&rightInfo!=null&&leftInfo.isFindP&&rightInfo.isFindQ){
            ancestor=x;
        }
        if(leftInfo!=null&&rightInfo!=null&&leftInfo.isFindQ&&rightInfo.isFindP){
            ancestor=x;
        }
        if(leftInfo!=null&&leftInfo.isFindP&&x==q){
            ancestor=x;
        }
        if(leftInfo!=null&&leftInfo.isFindQ&&x==p){
            ancestor=x;
        }
        if(rightInfo!=null&&rightInfo.isFindP&&x==q){
            ancestor=x;
        }
        if(rightInfo!=null&&rightInfo.isFindQ&&x==p){
            ancestor=x;
        }
        return new Info(isFindP,isFindQ,ancestor);
    }
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        return process(root,p,q).ancestor;
    }
}

二叉树的最近公共祖先

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public class Info{
        boolean isFindP;
        boolean isFindQ;
        TreeNode ancestor;
        public Info(boolean a,boolean b,TreeNode c){
            isFindP=a;
            isFindQ=b;
            ancestor=c;
        }
    }
    public Info process(TreeNode x,TreeNode p,TreeNode q){
        if(x==null){
            return new Info(false,false,null);
        }
        Info leftInfo=process(x.left,p,q);
        Info rightInfo=process(x.right,p,q);
        boolean isFindP=false;
        boolean isFindQ=false;
        TreeNode ancestor=null;
        isFindP=(leftInfo==null?false:leftInfo.isFindP)|(rightInfo==null?false:rightInfo.isFindP)|(x==p);
        isFindQ=(leftInfo==null?false:leftInfo.isFindQ)|(rightInfo==null?false:rightInfo.isFindQ)|(x==q);
        //p,q同时在x的左子树或者右子树上
        if(leftInfo!=null&&leftInfo.isFindP&&leftInfo.isFindQ){
            ancestor=leftInfo.ancestor;
        }
        if(rightInfo!=null&&rightInfo.isFindP&&rightInfo.isFindQ){
            ancestor=rightInfo.ancestor;
        }
        //p,q分别在x的左子树或者右子树上
        if(leftInfo!=null&&rightInfo!=null&&leftInfo.isFindP&&rightInfo.isFindQ){
            ancestor=x;
        }
        if(leftInfo!=null&&rightInfo!=null&&leftInfo.isFindQ&&rightInfo.isFindP){
            ancestor=x;
        }
       // p,q只能有一个在x的左子树或者右子树上
        if(leftInfo!=null&&leftInfo.isFindP&&x==q){
            ancestor=x;
        }
        if(leftInfo!=null&&leftInfo.isFindQ&&x==p){
            ancestor=x;
        }
        if(rightInfo!=null&&rightInfo.isFindP&&x==q){
            ancestor=x;
        }
        if(rightInfo!=null&&rightInfo.isFindQ&&x==p){
            ancestor=x;
        }
        return new Info(isFindP,isFindQ,ancestor);
    }
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        return process(root,p,q).ancestor;
    }
}

检查平衡性

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public class Info{
        public boolean isBalanced;
        public int height;
        public Info(boolean a,int b){
            isBalanced=a;
            height=b;
        }
    }
    public Info process(TreeNode x){
        if(x==null){
            return new Info(true,0);
        }
        Info leftInfo=process(x.left);
        Info rightInfo=process(x.right);
        int height=0;
        boolean isBalanced=false;
        height=Math.max((leftInfo==null?0:leftInfo.height),(rightInfo==null?0:rightInfo.height))+1;
        if((leftInfo==null?true:leftInfo.isBalanced)&&
            (rightInfo==null?true:rightInfo.isBalanced)&&
            Math.abs((leftInfo==null?0:leftInfo.height)-(rightInfo==null?0:rightInfo.height))<=1){
            isBalanced=true;
        }

        return new Info(isBalanced,height);
    }
    public boolean isBalanced(TreeNode root) {
        Info info=process(root);
        return info.isBalanced;
    }
}