最大二叉树

最大二叉树
具有大根堆性质的二叉树，在数组末尾添加元素 ，如果对应的节点最大，则对应的节点作为新的根节点
否则作为最右边的节点，作为原二叉树的右子树节点

class Solution {
    public TreeNode insertIntoMaxTree(TreeNode root, int val) {
        if(root==null||root.val<val){
            TreeNode p=new TreeNode(val);
            p.left=root;
            return p;
        }else{
            root.right=insertIntoMaxTree(root.right,val);
            return root;
        }
    }
}

删除根到叶节点路径上不足的节点

删除根到路径上不足的节点
如果某一个非叶节点作为不足节点删除，则该节点的所有的左孩子节点和右孩子节点都需要被删除
反过来，如果一个节点在自底向上递归的过程中左右孩子都被删除，则所有通过该节点到叶子结点的路径都小于limit 所以当前节点也应该被删除

class Solution {
    public TreeNode sufficientSubset(TreeNode root, int limit) {
        return dfs(root,0,limit);
    }
    public TreeNode dfs(TreeNode root,int sum,int limit){
        sum+=root.val;
        if(root.left==null&&root.right==null){
            if(sum<limit){
                root=null;
               // return null;//当前节点置为null
            }
        }else{
            if(root.left!=null){
                root.left=dfs(root.left,sum,limit);
            }
            if(root.right!=null){
                root.right=dfs(root.right,sum,limit);
            }
            if(root.left==null&&root.right==null){
                // return null;
                root=null;
            }
        }
        return root;
    }
}

删点成林 将二叉树指定节点删除

删点成林

 class Solution {
    List<TreeNode> res=new ArrayList<TreeNode>();
    Set<Integer> set=new HashSet<>();
    public List<TreeNode> delNodes(TreeNode root, int[] to_delete) {
        for(int i=0;i<to_delete.length;i++){
            set.add(to_delete[i]);
        }
        res.add(root);
        dfs(root);
        return res;
    }
    public TreeNode dfs(TreeNode root){
        if(root==null){
            return root;
        }
        root.left=dfs(root.left);
        root.right=dfs(root.right);
        if(set.contains(root.val)){

            if(root.left!=null){
                res.add(root.left);
            }
            if(root.right!=null){
                res.add(root.right);
            }
            //将root节点删除之后
            if(res.contains(root)){
                res.remove(root);
            }
            return null;
        }
        return root;
    }
}

最长同值路径

最长同值路径

 class Solution {
    int res=0;
    public int longestUnivaluePath(TreeNode root) {
        dfs(root);
        return res;
    }
    public int dfs(TreeNode root){
        if(root==null){
            return 0;
        }
        int left=dfs(root.left);int right=dfs(root.right);
        if(root.left==null||root.left.val!=root.val){
            left=0;
        }
        if(root.right==null||root.right.val!=root.val){
            right=0;
        }
        res=Math.max(res,left+right);
        return Math.max(left,right)+1;
    }
}

二叉树的剪枝 将所有节点值都是0的子树进行剪枝

二叉树剪枝

 class Solution {
    public TreeNode pruneTree(TreeNode root) {
        //通过剪枝递归的方式
        return dfs(root);

    }
    public TreeNode dfs(TreeNode root){
        if(root==null){
            return null;
        }
        root.left=dfs(root.left);
        root.right=dfs(root.right);
        return (root.left==null&&root.right==null&&root.val==0)? null:root;
    }
}

方式二 递归函数返回对应的剪枝条件

class Solution {
    public TreeNode pruneTree(TreeNode root) {
        //通过返回boolean进行剪枝
        return dfs(root)? null:root;
    }
    public boolean dfs(TreeNode root){
        if(root==null){
            return true;
        }
        boolean left=dfs(root.left);
        boolean right=dfs(root.right);
        if(left){
            root.left=null;
        }
        if(right){
            root.right=null;
        }
        return left&&right&&root.val==0;
    }
}

修剪二叉树

修剪二叉树

 class Solution {
    public TreeNode trimBST(TreeNode root, int low, int high) {
        return dfs(root,low,high);
    }
    public TreeNode dfs(TreeNode root,int low,int high){
        if(root==null){
            return root;
        }

        root.left=dfs(root.left,low,high);
        root.right=dfs(root.right,low,high);

        if(root.val<low){
            return dfs(root.right,low,high);
        }
        if(root.val>high){
            return dfs(root.left,low,high);
        }

        return root;

    }
}