leetcode--树

1.树的递归

1二叉树的最大深度(104)

给定一个二叉树找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

public class Solution {

    public static void main(String[] args) {
        TreeNode tree=new TreeNode(1,new TreeNode(2),new TreeNode(3));
        Solution solution=new Solution();
        System.out.println(solution.maxDepth(tree));
    }

    public int maxDepth(TreeNode root) {
        int maxLength=0;
        return dfs(root,maxLength);
    }

    private int dfs(TreeNode root,int maxLength){
        if (root==null){
            return 0;
        }
        int leftLength=dfs(root.left,maxLength);//计算左子树的高度
        int rightLength=dfs(root.right,maxLength);//计算右子树的高度
        maxLength=Math.max(maxLength,Math.max(leftLength,rightLength)+1);
        return maxLength;
    }

}

2平衡二叉树(110)

给定一个二叉树判断它是否是高度平衡的二叉树。

本题中一棵高度平衡二叉树定义为

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。

输入root = [3,9,20,null,null,15,7]
输出true

输入root = []
输出true

输入root = [1,2,2,3,3,null,null,4,4]
输出false

//自顶向下递归
    public boolean isBalanced(TreeNode root) {
        if (root==null){
            return true;
        }
        //首先计算左右子树高度,如果左右子树高度差不超过1,再分别递归遍历左右子节点,并判断是否平衡
        return Math.abs(getHeight(root.left)-getHeight(root.right))<=1&&isBalanced(root.left)&&isBalanced(root.right);
    }

    //得到以某个节点开始子树的高度
    private int getHeight(TreeNode root){
        if (root==null){
            return 0;
        }
        int leftHeight=getHeight(root.left);//得到左子树的高度
        int rightHeight=getHeight(root.right);//得到右子树的高度
        return Math.max(leftHeight,rightHeight)+1;
    }

//自底向上递归
public class Solution {

    public static void main(String[] args) {
        TreeNode tree=new TreeNode(1,new TreeNode(2),new TreeNode(3));
        Solution solution=new Solution();
        System.out.println(solution.isBalanced(tree));
    }

    public boolean isBalanced(TreeNode root) {
        if (root==null){
            return true;
        }
        return getHeight(root)>=0;
    }

    private int getHeight(TreeNode root){
        if (root==null){
            return 0;
        }
        int leftHeight=getHeight(root.left);//得到左子树的高度
        int rightHeight=getHeight(root.right);//得到右子树的高度
        if (leftHeight==-1||rightHeight==-1||Math.abs(leftHeight-rightHeight)>1){
            return -1;
        }
        return Math.max(leftHeight,rightHeight)+1;
    }

}

3二叉树的直径(543)

给定一棵二叉树你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。

public class Solution {

    int maxNodes=1;//二叉树两个节点间的节点数最大值

    public static void main(String[] args) {
        TreeNode tree=new TreeNode(1,new TreeNode(2),new TreeNode(3));
        Solution solution=new Solution();
        System.out.println(solution.diameterOfBinaryTree(tree));
    }

    public int diameterOfBinaryTree(TreeNode root) {
        getDepth(root);
        return maxNodes-1;
    }

    private int getDepth(TreeNode root) {
        if (root==null){
            return 0;
        }
        int leftDepth=getDepth(root.left);//左子树的高度
        int rightDepth=getDepth(root.right);//右子树的高度
        //更新最大值
        maxNodes=Math.max(maxNodes,leftDepth+rightDepth+1);
        return Math.max(leftDepth,rightDepth)+1;
    }

}

4路径总和 III(437)

给定一个二叉树的根节点 root 和一个整数 targetSum 求该二叉树里节点值之和等于 targetSum 的 路径 的数目。

路径 不需要从根节点开始也不需要在叶子节点结束但是路径方向必须是向下的只能从父节点到子节点。

输入root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
输出3
解释和等于 8 的路径有 3 条如图所示。

public class Solution {

    public static void main(String[] args) {
        TreeNode tree=new TreeNode(1,new TreeNode(2),new TreeNode(3));
        Solution solution=new Solution();
        int sum=2;
        System.out.println(solution.pathSum(tree,sum));
    }

    public int pathSum(TreeNode root, int targetSum) {
        if (root==null){
            return 0;
        }
        int count=getCount(root,targetSum);//二叉树里节点值之和等于 targetSum 的 路径 的数目
        //还需要加上以左右子树为头节点的二叉树上的数目
        count+=getCount(root.left,targetSum);
        count+=getCount(root.right,targetSum);
        return count;
    }

    private int getCount(TreeNode root,long targetSum){
        int count=0;
        if (root==null){//递归退出条件 未找到路径
            return 0;
        }
        int val= root.val;
        if (val==targetSum){//递归退出条件 找到一个路径
            count++;
        }
        //从当前节点的左节点开始找
        count+=getCount(root.left,targetSum-val);
        //从当前节点的右节点开始找
        count+=getCount(root.right,targetSum-val);
        return count;
    }

}

5对称二叉树(101)

给你一个二叉树的根节点 root 检查它是否轴对称。

输入root = [1,2,2,3,4,4,3]
输出true

输入root = [1,2,2,null,3,null,3]
输出false

//递归
public class Solution {

    public static void main(String[] args) {
        TreeNode tree=new TreeNode(1,new TreeNode(2),new TreeNode(3));
        Solution solution=new Solution();
        System.out.println(solution.isSymmetric(tree));
    }

    public boolean isSymmetric(TreeNode root) {
        return check(root,root);
    }

    //每次检查l和r节点的值是否相等 如果相等,再判断它们的左右子树是否对称
    private boolean check(TreeNode l, TreeNode r) {
        if (l==null&&r==null){
            return true;
        }
        if (l==null||r==null){//当某个节点为null时 与他对应的节点不为null 则不是对称二叉树
            return false;
        }
        return l.val==r.val&&check(l.left,r.right)&&check(l.right,r.left);
    }

}


//迭代
public class Solution {

    public static void main(String[] args) {
        TreeNode tree=new TreeNode(1,new TreeNode(2),new TreeNode(3));
        Solution solution=new Solution();
        System.out.println(solution.isSymmetric(tree));
    }

    public boolean isSymmetric(TreeNode root) {
        return check(root,root);
    }

    private boolean check(TreeNode l, TreeNode r) {
        Queue<TreeNode> queue=new LinkedList<>();
        queue.add(l);
        queue.add(r);
        while (!queue.isEmpty()){
            l=queue.poll();
            r=queue.poll();
            //当两个都为空时 继续从队列中弹出元素 因为在叶子节点会将null加入队列
            if (l==null&&r==null){
                continue;
            }
            //当有一个为null另一个不为null 或者它们的值不相等时
            if ((l==null||r==null)||l.val!=r.val){
                return false;
            }

            //继续加入节点
            queue.add(l.left);
            queue.add(r.right);

            queue.add(l.right);
            queue.add(r.left);
        }
        return true;
    }

}

6删点成林(1110)

给出二叉树的根节点 root树上每个节点都有一个不同的值。

如果节点值在 to_delete 中出现我们就把该节点从树上删去最后得到一个森林一些不相交的树构成的集合。

返回森林中的每棵树。你可以按任意顺序组织答案。

输入root = [1,2,3,4,5,6,7], to_delete = [3,5]
输出[[1,2,null,4],[6],[7]]

2.层次遍历

1二叉树的层平均值(637)

给定一个非空二叉树的根节点 root , 以数组的形式返回每一层节点的平均值。与实际答案相差 10-5 以内的答案可以被接受。

输入root = [3,9,20,null,null,15,7]
输出[3.00000,14.50000,11.00000]
解释第 0 层的平均值为 3,第 1 层的平均值为 14.5,第 2 层的平均值为 11 。
因此返回 [3, 14.5, 11] 。

//BFS
public class Solution {

    public static void main(String[] args) {
        TreeNode tree=new TreeNode(1,new TreeNode(2),new TreeNode(3));
        Solution solution=new Solution();
        System.out.println(solution.averageOfLevels(tree));
    }

    public List<Double> averageOfLevels(TreeNode root) {
        List<Double> list=new ArrayList<>();//存储层平均值
        Queue<TreeNode> queue=new LinkedList<>();//存储树的节点
        queue.add(root);//头节点加入队列
        while (!queue.isEmpty()){
            int size=queue.size();//计算当前层的元素个数
            double sum=0;//当前层的元素和
            for (int i=0;i<size;i++){
                TreeNode node=queue.poll();//弹出队首元素
                sum+= node.val;
                //如果当前节点的左右节点不为null 将当前节点的左右节点加入队列
                if (node.left!=null){
                    queue.add(node.left);
                }
                if (node.right!=null){
                    queue.add(node.right);
                }
            }
            list.add(sum/size);
        }
        return list;
    }
}

3.前中后序遍历

1从前序与中序遍历序列构造二叉树(105)

给定两个整数数组 preorder 和 inorder 其中 preorder 是二叉树的先序遍历 inorder 是同一棵树的中序遍历请构造二叉树并返回其根节点。

输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]

输入: preorder = [-1], inorder = [-1]
输出: [-1]

public class Solution {

    public static void main(String[] args) {
        TreeNode tree=new TreeNode(1,new TreeNode(2),new TreeNode(3));
        Solution solution=new Solution();
        int[] arr1={3,9,20,15,7};
        int[] arr2={9,3,15,20,7};
        System.out.println(solution.buildTree(arr1,arr2));
    }

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int n= preorder.length;
        Map<Integer,Integer> map=new HashMap<>();//保存中序遍历中变量的值以及其出现的位置
        for (int i=0;i<n;i++){
            map.put(inorder[i],i);
        }
        //构建树
        return getTree(preorder,inorder,0,n-1,0,n-1,map);
    }

    private TreeNode getTree(int[] preorder, int[] inorder, int preorderLeft, int preorderRight, int inorderLeft, int inorderRight,Map<Integer,Integer> map) {
        if (preorderLeft>preorderRight){
            return null;
        }
        //先序遍历的第一个节点就是根节点
        int preorderRoot=preorderLeft;//根节点在先序遍历中的位置
        //在中序遍历中找到根节点的位置
        int inorderRoot=map.get(preorder[preorderRoot]);//根节点在中序遍历中的位置

        //构建根节点
        TreeNode root=new TreeNode(preorder[preorderRoot]);
        //左子树中的节点数目
        int sizeLeft=inorderRoot-inorderLeft;
        //递归的构造左子树 并连接到根节点
        //先序遍历中 [从左边界+1开始的sizeLeft个元素] 对应中序遍历中[左边界,根节点定位-1]的元素
        root.left=getTree(preorder,inorder,preorderLeft+1,preorderLeft+sizeLeft,inorderLeft,inorderRoot-1,map);
        //递归构造右子树 并连接到根节点
        //先序遍历中 [从左边界+1+左子树数目开始到有边界] 的元素对应了中序遍历中[从根节点定位+1 到 有边界]的元素
        root.right=getTree(preorder,inorder,preorderLeft+1+sizeLeft,preorderRight,inorderRoot+1,inorderRight,map);
        return root;
    }
}

2二叉树的前序遍历(144)

给你二叉树的根节点 root 返回它节点值的 前序 遍历。

//递归
public class Solution {

    public static void main(String[] args) {
        TreeNode tree=new TreeNode(1,new TreeNode(2),new TreeNode(3));
        Solution solution=new Solution();
        System.out.println(solution.preorderTraversal(tree));
    }

    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list=new ArrayList<>();
        getPreorder(root,list);
        return list;
    }

    private void getPreorder(TreeNode root, List<Integer> list) {
        if (root==null){
            return;
        }
        list.add(root.val);//
        getPreorder(root.left,list);//递归遍历左子树
        getPreorder(root.right,list);//递归遍历右子树
    }
}


//非递归
public class Solution {

    public static void main(String[] args) {
        TreeNode tree=new TreeNode(1,new TreeNode(2),new TreeNode(3));
        Solution solution=new Solution();
        System.out.println(solution.preorderTraversal(tree));
    }

    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list=new ArrayList<>();
        if (root==null){
            return list;
        }
        Stack<TreeNode> stack=new Stack<>();
        stack.push(root);//因为是先序遍历 将根节点先加入栈
        while (!stack.isEmpty()){
            TreeNode node=stack.pop();//弹出栈顶元素
            list.add(node.val);
            if (node.right!=null){//先将当前节点的右孩子入栈
                stack.push(node.right);
            }
            if (node.left!=null){//再将当前节点的左孩子入栈
                stack.push(node.left);
            }
        }
        return list;
    }

}

4.二叉查找树

1恢复二叉搜索树

给你二叉搜索树的根节点 root 该树中的 恰好 两个节点的值被错误地交换。请在不改变其结构的情况下恢复这棵树 。

输入root = [1,3,null,null,2]
输出[3,1,null,null,2]
解释3 不能是 1 的左孩子因为 3 > 1 。交换 1 和 3 使二叉搜索树有效。

输入root = [3,1,4,null,null,2]
输出[2,1,4,null,null,3]
解释2 不能在 3 的右子树中因为 2 < 3 。交换 2 和 3 使二叉搜索树有效。

public class Solution {

    public static void main(String[] args) {
        TreeNode tree=new TreeNode(1,new TreeNode(2),new TreeNode(3));
        Solution solution=new Solution();
        solution.recoverTree(tree);
        System.out.println(tree);
    }

    public void recoverTree(TreeNode root) {
        List<Integer> arr=new ArrayList<>();//用来存储二叉树中序遍历的结果
        //中序遍历二叉树
        getInorderTraversal(root,arr);
        //得到错误被交换的两个节点
        int[] nums = getTwoErrorNodes(arr);
        //在二叉树中还原被交换错误的节点
        getCorrectTree(root,2,nums[0],nums[1]);
    }

    //得到二叉树的中序遍历结果
    private void getInorderTraversal(TreeNode root,List<Integer> arr){
        if (root==null){
            return;
        }
        getInorderTraversal(root.left,arr);
        arr.add(root.val);
        getInorderTraversal(root.right,arr);
    }

    //得到错误被交换的两个节点
    private int[] getTwoErrorNodes(List<Integer> arr){
        int n= arr.size()-1;
        int index1=-1,index2=-1;//被错误交换的两个节点在数组的索引
        for (int i=0;i<n;i++){
            if (arr.get(i)> arr.get(i+1)){//当出现非递增的情况
                index2=i+1;
                if (index1==-1){
                    index1=i;
                }else {//当被交换的节点已经全部找到时 退出遍历
                    break;
                }
            }
        }
        return new int[]{arr.get(index1),arr.get(index2)};
    }

    //还原二叉树
    private void getCorrectTree(TreeNode root,int counts,int errorNode1,int errorNode2){
        if (root!=null){
            //当找到错误节点时 交换节点的值
            if (root.val==errorNode1||root.val==errorNode2){
                root.val=root.val==errorNode1?errorNode2:errorNode1;
                //当两个错误节点都找到时 退出
                if (counts--==0){
                    return;
                }
            }
            getCorrectTree(root.left,counts,errorNode1,errorNode2);//递归遍历左子树
            getCorrectTree(root.right,counts,errorNode1,errorNode2);//递归遍历右子树
        }
    }

}

2修剪二叉搜索树

给你二叉搜索树的根节点 root 同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树使得所有节点的值在[low, high]中。修剪树 不应该 改变保留在树中的元素的相对结构 (即如果没有被移除原有的父代子代关系都应当保留)。 可以证明存在 唯一的答案 。

所以结果应当返回修剪好的二叉搜索树的新的根节点。注意根节点可能会根据给定的边界发生改变。

输入root = [1,0,2], low = 1, high = 2
输出[1,null,2]

输入root = [3,0,4,null,2,null,null,1], low = 1, high = 3
输出[3,2,null,1]

//递归
public class Solution {

    public static void main(String[] args) {
        TreeNode tree=new TreeNode(1,new TreeNode(2),new TreeNode(3));
        Solution solution=new Solution();
        System.out.println(solution.trimBST(tree,1,2));
    }

    public TreeNode trimBST(TreeNode root, int low, int high) {
        if(root==null){
            return null;
        }
        if (root.val<low){//当节点的值小于左边界
            //则它以及它的左子树都需要修剪 则返回对它的右子树的修剪结果
            return trimBST(root.right,low,high);
        }else if (root.val>high){//当节点的值大于右边界
            //则它以及它的右子树都需要修剪 则返回对它的左子树的修剪结果
            return trimBST(root.left,low,high);
        }else {//节点值位于区间
            root.left=trimBST(root.left,low,high);
            root.right=trimBST(root.right,low,high);
            return root;
        }
    }

}


//迭代
public class Solution {

    public static void main(String[] args) {
        TreeNode tree=new TreeNode(1,new TreeNode(2),new TreeNode(3));
        Solution solution=new Solution();
        System.out.println(solution.trimBST(tree,1,2));
    }

    public TreeNode trimBST(TreeNode root, int low, int high) {
        //当 当前 头节点不满足给定范围时
        while (root!=null&&(root.val<low||root.val>high)){
            if (root.val<low){//如果当前头结点的值小于low
                //更改头节点为当前头节点的右节点
                root=root.right;
            }else {//如果当前头节点的值大于high
                //更改头节点为当前头节点的左节点
                root=root.left;
            }
        }
        if (root==null){
            return null;
        }
        //当头节点在给定范围时 修剪它的左子树
        for (TreeNode node=root;node.left!=null;){
            if (node.left.val<low){//当node的左节点的值小于low时
                //不更改node 继续以当前node为头节点进行判断
                node.left=node.left.right;
            }else {
                //修改当前节点为当前节点的左节点
                node=node.left;
            }
        }
        //当头节点在给定范围时 修剪它的右子树
        for (TreeNode node=root;node.right!=null;){
            if (node.right.val>high){
                node.right=node.right.left;
            }else {
                node=node.right;
            }
        }
        return root;
    }

}

5.字典树

字典树用于判断字符串是否存在或者是否具有某种字符串前缀

1实现 Trie (前缀树)(208)

Trie发音类似 “try”或者说 前缀树 是一种树形数据结构用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景例如自动补完和拼写检查。

请你实现 Trie 类

Trie() 初始化前缀树对象。
void insert(String word) 向前缀树中插入字符串 word 。
boolean search(String word) 如果字符串 word 在前缀树中返回 true即在检索之前已经插入否则返回 false 。
boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix 返回 true 否则返回 false 。

public class Trie {

    private Trie[] children;//指向子节点的指针数组
    private boolean isEnd;//表示该节点是否为字符串的末尾 true:是字符串的末尾

    public Trie() {
        children=new Trie[26];
        isEnd=false;
    }

    public void insert(String word) {
        Trie node=this;
        for (int i=0;i<word.length();i++){
            char ch=word.charAt(i);
            int index=ch-'a';
            if (node.children[index]==null){
                node.children[index]=new Trie();
            }
            node=node.children[index];
        }
        node.isEnd=true;
    }

    public boolean search(String word) {
        Trie node=searchPrefix(word);
        return node!=null&& node.isEnd;
    }

    public boolean startsWith(String prefix) {
        return searchPrefix(prefix)!=null;
    }

    private Trie searchPrefix(String word) {
        Trie node=this;
        for (int i=0;i<word.length();i++){
            char ch=word.charAt(i);
            int index=ch-'a';
            if (node.children[index]==null){
                return null;
            }
            node= node.children[index];
        }
        return node;
    }

}

6.练习

1翻转二叉树(226)

给你一棵二叉树的根节点 root 翻转这棵二叉树并返回其根节点。

public class Solution {

    public static void main(String[] args) {
        TreeNode tree=new TreeNode(1,new TreeNode(2),new TreeNode(3));
        Solution solution=new Solution();
        System.out.println(solution.invertTree(tree));
    }

    public TreeNode invertTree(TreeNode root) {
        if (root==null){
            return null;
        }
        TreeNode left=invertTree(root.left);//翻转左子树
        TreeNode right=invertTree(root.right);//翻转右子树
        root.left=right;
        root.right=left;
        return root;
    }
}

2合并二叉树(617)

给你两棵二叉树 root1 和 root2 。

想象一下当你将其中一棵覆盖到另一棵之上时两棵树上的一些节点将会重叠而另一些不会。你需要将这两棵树合并成一棵新二叉树。合并的规则是如果两个节点重叠那么将这两个节点的值相加作为合并后节点的新值否则不为 null 的节点将直接作为新二叉树的节点。

返回合并后的二叉树。

注意: 合并过程必须从两个树的根节点开始。

public class Solution {

    public static void main(String[] args) {
        TreeNode tree=new TreeNode(1,new TreeNode(2),new TreeNode(3));
        Solution solution=new Solution();
        System.out.println(solution.mergeTrees(tree,tree));
    }

    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if (root1==null){
            return root2;
        }
        if (root2==null){
            return root1;
        }
        TreeNode merged=new TreeNode(root1.val+ root2.val);
        merged.left=mergeTrees(root1.left,root2.left);//递归合并左子树
        merged.right=mergeTrees(root1.right, root2.right);//递归合并右子树
        return merged;
    }
}

3另一棵树的子树

给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在返回 true 否则返回 false 。

二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树

//暴力匹配 从root的每一个节点出发判断subRoot是否是root的子树
public class Solution {

    public static void main(String[] args) {
        TreeNode tree=new TreeNode(1,new TreeNode(2),new TreeNode(3));
        Solution solution=new Solution();
        System.out.println(solution.isSubtree(tree,tree));
    }

    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        //递归root的每一个节点 判断从当前节点出发subRoot是否是root的子树
        return dfs(root,subRoot);
    }

    private boolean dfs(TreeNode root, TreeNode subRoot) {
        if (root==null){
            return false;
        }
        return check(root,subRoot)||dfs(root.left,subRoot)||dfs(root.right,subRoot);
    }

    //判断从当前节点出发 subRoot是否是root的子树
    private boolean check(TreeNode root,TreeNode subRoot){
        if (root==null&&subRoot==null){
            return true;
        }
        if (root==null||subRoot==null){
            return false;
        }
        //当 当前 节点值相等时 判断它们的左右子树是否相等
        if (root.val== subRoot.val){
            return check(root.left,subRoot.left)&&check(root.right,subRoot.right);
        }
        return false;
    }
}


//根据先序遍历的序列做字符串匹配 用KMP
public class Solution {

    public static void main(String[] args) {
        TreeNode tree=new TreeNode(1,new TreeNode(2),new TreeNode(3));
        Solution solution=new Solution();
        System.out.println(solution.isSubtree(tree,tree));
    }

    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        List<Integer> rootList=new ArrayList<>();//用来存储root的先序遍历序列
        List<Integer> subRootList=new ArrayList<>();//用来存储subRoot的先序遍历序列
        //因为题目所给数据的最大值为10^4
        int leftNull=10001;
        int rightNull=10002;
        getList(root,rootList,leftNull,rightNull);
        getList(subRoot,subRootList,leftNull,rightNull);
        return kmp(rootList,subRootList);
    }

    //得到二叉树的先序遍历序列
    private void getList(TreeNode root,List<Integer> list,int leftNull,int rightNull){
        if (root==null){
            return;
        }
        list.add(root.val);
        if (root.left!=null){
            //对左子树进行先序遍历
            getList(root.left, list, leftNull, rightNull);
        }else {
            list.add(leftNull);
        }
        if (root.right!=null){
            //对右子树进行先序遍历
            getList(root.right, list, leftNull, rightNull);
        }else {
            list.add(rightNull);
        }
    }

    //使用KMP判断subRootList是否是rootList的子串
    private boolean kmp(List<Integer> rootList, List<Integer> subRootList) {
        int rootLength= rootList.size();
        int subLength= subRootList.size();
        int[] next=new int[subLength];//辅助数组
        Arrays.fill(next,-1);
        //更新next数组的值
        for (int i=1,j=-1;i<subLength;i++){
            while (j!=-1&&!(subRootList.get(i).equals(subRootList.get(j+1)))){
                j=next[j];
            }
            if (subRootList.get(i).equals(subRootList.get(j+1))){
                j++;
            }
            next[i]=j;
        }
        //是否可以匹配到
        for (int i=0,j=-1;i<rootLength;i++){
            while (j!=-1&&!(rootList.get(i).equals(subRootList.get(j+1)))){
                j=next[j];
            }
            if (rootList.get(i).equals(subRootList.get(j+1))){
                j++;
            }
            if (j==subLength-1){
                return true;
            }
        }
        return false;
    }

}

4左叶子之和(404)

给定二叉树的根节点 root 返回所有左叶子之和。

输入: root = [3,9,20,null,null,15,7] 
输出: 24 
解释: 在这个二叉树中有两个左叶子分别是 9 和 15所以返回 24

输入: root = [1]
输出: 0

public class Solution {

    public static void main(String[] args) {
        TreeNode tree=new TreeNode(1,new TreeNode(2),new TreeNode(3));
        Solution solution=new Solution();
        System.out.println(solution.sumOfLeftLeaves(tree));
    }

    public int sumOfLeftLeaves(TreeNode root) {
        if (root==null){
            return 0;
        }
        int sum=0;
        if (root.left!=null&&root.left.left==null&&root.left.right==null){
            sum+=root.left.val;
        }
        return sum+sumOfLeftLeaves(root.left)+sumOfLeftLeaves(root.right);
    }

}

5找树左下角的值(513)

给定一个二叉树的 根节点 root请找出该二叉树的 最底层 最左边 节点的值。

假设二叉树中至少有一个节点。

输入: root = [2,1,3]
输出: 1

输入: [1,2,3,4,null,5,6,null,null,7]
输出: 7

//深度优先遍历 维护一个当前高度
public class Solution {

    int curHeight=0;//当前最左值的层高
    int curVal=0;//当前最左值

    public static void main(String[] args) {
        TreeNode tree=new TreeNode(1,new TreeNode(2),new TreeNode(3));
        Solution solution=new Solution();
        System.out.println(solution.findBottomLeftValue(tree));
    }

    public int findBottomLeftValue(TreeNode root) {
        dfs(root,0);
        return curVal;
    }

    private void dfs(TreeNode root, int height) {
        if (root==null){
            return;
        }
        height++;
        dfs(root.left,height);//递归左子树找最左值
        dfs(root.right,height);//递归右子树找最左值
        //当此时树高大于当前最大树高时
        if (height>curHeight){
            curHeight=height;
            curVal= root.val;
        }
    }

}


//宽度优先遍历 从右到左将节点加入队列 最后一个节点就是最底层最左边的节点的值
public class Solution {

    public static void main(String[] args) {
        TreeNode tree=new TreeNode(1,new TreeNode(2),new TreeNode(3));
        Solution solution=new Solution();
        System.out.println(solution.findBottomLeftValue(tree));
    }

    public int findBottomLeftValue(TreeNode root) {
        Queue<TreeNode> queue=new LinkedList<>();
        int result=0;
        queue.add(root);
        while (!queue.isEmpty()){
            TreeNode node = queue.poll();//弹出队首节点
            //首先加入当前队首节点的右孩子
            if (node.right!=null){
                queue.add(node.right);
            }
            //加入当前队首节点的左孩子
            if (node.left!=null){
                queue.add(node.left);
            }
            result= node.val;
        }
        return result;
    }

}

6把二叉搜索树转换为累加树(538)

给出二叉 搜索 树的根节点该树的节点值各不相同请你将其转换为累加树Greater Sum Tree使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。

//保存中序遍历的结果 再更改二叉树
public class Solution {

    public static void main(String[] args) {
        TreeNode tree=new TreeNode(2,new TreeNode(1),new TreeNode(3));
        Solution solution=new Solution();
        System.out.println(solution.convertBST(tree));
    }

    public TreeNode convertBST(TreeNode root) {
        if (root==null){
            return null;
        }
        List<Integer> list=new ArrayList<>();//保存二叉树的遍历序列
        //得到二叉树中序遍历的序列 从小到大排列
        getRootList(root,list);
        int sum=0;//二叉树所有节点之和
        //key:原二叉树节点的值  value:每个节点的新值
        Map<Integer,Integer> map=new HashMap<>();
        for (int i:list){
            sum+=i;
        }
        map.put(list.get(0),sum);
        for (int i=1;i<list.size();i++){
            sum-= list.get(i-1);
            map.put(list.get(i),sum);
        }
        //将二叉搜索树转换为二叉累加树
        changeTree(root,map);
        return root;
    }

    //得到二叉树的中序遍历的序列
    private void getRootList(TreeNode root,List<Integer> list){
        if (root==null){
            return;
        }
        getRootList(root.left,list);
        list.add(root.val);
        getRootList(root.right,list);
    }

    //将二叉搜索树转换为二叉累加树
    private void changeTree(TreeNode root,Map<Integer,Integer> map){
        if (root==null){
            return;
        }
        changeTree(root.left,map);//转换左子树
        root.val=map.get(root.val);//改变值
        changeTree(root.right,map);//转换右子树
    }
    
}


//反序中序遍历二叉树 直接更改二叉树
public class Solution {

    int sum=0;

    public static void main(String[] args) {
        TreeNode tree=new TreeNode(2,new TreeNode(1),new TreeNode(3));
        Solution solution=new Solution();
        System.out.println(solution.convertBST(tree));
    }

    public TreeNode convertBST(TreeNode root) {
        if (root!=null){
            convertBST(root.right);//先修改右子树
            sum+= root.val;
            root.val=sum;//修改值
            convertBST(root.left);//修改左子树
        }
        return root;
    }
}

7二叉搜索树的最近公共祖先(235)

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6 
解释: 节点 2 和节点 8 的最近公共祖先是 6。

//两次遍历
public class Solution {

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        List<TreeNode> pathP = getPath(root, p);
        List<TreeNode> pathQ = getPath(root, q);
        TreeNode ancestor=null;//最近公共祖先
        for (int i=0;i<pathP.size()&&i<pathQ.size();i++){
            if (pathP.get(i)==pathQ.get(i)){
                ancestor=pathP.get(i);
            }
        }
        return ancestor;
    }

    //得到根节点到目标节点的路径
    private List<TreeNode> getPath(TreeNode root,TreeNode target){
        List<TreeNode> list=new ArrayList<>();
        while (root!=target){
            list.add(root);
            //当前节点的值小于目标节点的值时 就从当前节点的右孩子开始找
            if (root.val< target.val){
                root=root.right;
            }else {//从左孩子开始找
                root=root.left;
            }
        }
        list.add(root);
        return list;
    }
}


//一次遍历
public class Solution {

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        while (root!=null){
            //当前节点小于p和q时 找当前节点的右子树
            if (root.val<p.val&&root.val<q.val){
                root=root.right;
            } else if (root.val>p.val&&root.val>q.val) {//当前节点大于p和q时 找当前节点的左子树
                root=root.left;
            }else {
                //当前边两个条件都不满足时 证明找到了分叉点也就是最低公共祖先
                break;
            }
        }
        return root;
    }

}

8二叉搜索树的最小绝对差

给你一个二叉搜索树的根节点 root 返回 树中任意两不同节点值之间的最小差值 。

差值是一个正数其数值等于两值之差的绝对值。

输入root = [4,2,6,1,3]
输出1

//保存中序遍历的序列
public class Solution {

    public static void main(String[] args) {
        TreeNode tree=new TreeNode(2,new TreeNode(1),new TreeNode(3));
        Solution solution=new Solution();
        System.out.println(solution.getMinimumDifference(tree));
    }

    public int getMinimumDifference(TreeNode root) {
        //保存二叉树的中序遍历序列
        List<Integer> path=new ArrayList<>();
        getPath(root,path);
        int minNum=Integer.MAX_VALUE;
        for (int i=1;i<path.size();i++){
            minNum=Math.min(minNum,path.get(i)-path.get(i-1));
        }
        return minNum;
    }

    //得到二叉树的中序遍历序列
    private void getPath(TreeNode root,List<Integer> list){
        if (root==null){
            return;
        }
        getPath(root.left,list);//左子树的中序遍历序列
        list.add(root.val);
        getPath(root.right,list);//右子树的中序遍历序列
    }

}


//不保存中序遍历的序列
public class Solution {

    int preVal;//前一个节点的值
    int minNum;//最小差值

    public static void main(String[] args) {
        TreeNode tree=new TreeNode(2,new TreeNode(1),new TreeNode(3));
        Solution solution=new Solution();
        System.out.println(solution.getMinimumDifference(tree));
    }

    public int getMinimumDifference(TreeNode root) {
        minNum=Integer.MAX_VALUE;
        preVal=-1;
        getPath(root);
        return minNum;
    }

    //得到二叉树的中序遍历序列
    private void getPath(TreeNode root){
        if (root==null){
            return;
        }
        getPath(root.left);//左子树的中序遍历序列
        if (preVal==-1){
            preVal=root.val;
        }else {
            minNum=Math.min(minNum,root.val-preVal);
            preVal= root.val;
        }
        getPath(root.right);//右子树的中序遍历序列
    }

}

9根据前序和后序遍历构造二叉树(889)

给定两个整数数组preorder 和 postorder 其中 preorder 是一个具有 无重复 值的二叉树的前序遍历postorder 是同一棵树的后序遍历重构并返回二叉树。

如果存在多个答案您可以返回其中 任何 一个。

输入preorder = [1,2,4,5,3,6,7], postorder = [4,5,2,6,7,3,1]
输出[1,2,3,4,5,6,7]

public class Solution {

    public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {
        int N=preorder.length;
        if (N==0){
            return null;
        }
        TreeNode root=new TreeNode(preorder[0]);
        if (N==1){
            return root;
        }
        int L=0;
        for (int i=0;i<N;i++){
            if (preorder[1]==postorder[i]){
                //求出左子树的节点个数 也就是在数组中的长度
                L=i+1;
            }
        }
        root.left=constructFromPrePost(Arrays.copyOfRange(preorder,1,L+1),
                                       Arrays.copyOfRange(postorder,0,L));
        root.right=constructFromPrePost(Arrays.copyOfRange(preorder,L+1,N),
                                        Arrays.copyOfRange(postorder,L,N-1));
        return root;
    }
}

10从中序与后序遍历序列构造二叉树(106)

给定两个整数数组 inorder 和 postorder 其中 inorder 是二叉树的中序遍历 postorder 是同一棵树的后序遍历请你构造并返回这颗 二叉树 。

输入inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
输出[3,9,20,null,null,15,7]

class Solution {
    int post_idx;
    int[] postorder;
    int[] inorder;
    Map<Integer, Integer> idx_map = new HashMap<Integer, Integer>();

    public TreeNode helper(int in_left, int in_right) {
        // 如果这里没有节点构造二叉树了就结束
        if (in_left > in_right) {
            return null;
        }

        // 选择 post_idx 位置的元素作为当前子树根节点
        int root_val = postorder[post_idx];
        TreeNode root = new TreeNode(root_val);

        // 根据 root 所在位置分成左右两棵子树
        int index = idx_map.get(root_val);

        // 下标减一
        post_idx--;
        // 构造右子树
        root.right = helper(index + 1, in_right);
        // 构造左子树
        root.left = helper(in_left, index - 1);
        return root;
    }

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        this.postorder = postorder;
        this.inorder = inorder;
        // 从后序遍历的最后一个元素开始
        post_idx = postorder.length - 1;

        // 建立元素下标键值对的哈希表
        int idx = 0;
        for (Integer val : inorder) {
            idx_map.put(val, idx++);
        }
        
        return helper(0, inorder.length - 1);
    }
}

11二叉树的中序遍历(94)

给定一个二叉树的根节点 root 返回 它的 中序 遍历 。

//递归
public class Solution {

    public static void main(String[] args) {
        TreeNode tree=new TreeNode(2,new TreeNode(1),new TreeNode(3));
        Solution solution=new Solution();
        System.out.println(solution.inorderTraversal(tree));
    }

    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> path=new ArrayList<>();
        getPath(root,path);
        return path;
    }

    private void getPath(TreeNode root,List<Integer> list){
        if (root==null){
            return;
        }
        getPath(root.left,list);
        list.add(root.val);
        getPath(root.right,list);
    }
}


//迭代
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> path=new ArrayList<>();
        Stack<TreeNode> stack=new Stack<>();
        while (root!=null||!stack.isEmpty()){
            //一直遍历直到将当前节点以及其所有的左侧节点全加入栈
            while (root!=null){
                stack.push(root);
                root=root.left;
            }
            root=stack.pop();
            path.add(root.val);
            root=root.right;
        }
        return path;
    }


//Morris 中序遍历

12二叉树的最近公共祖先(236)

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

输入root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出3
解释节点 5 和节点 1 的最近公共祖先是节点 3 。

//递归
public class Solution {

    private TreeNode ans;

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        ans=null;
        dfs(root, p, q);
        return ans;
    }

    private boolean dfs(TreeNode root, TreeNode p, TreeNode q){
        if (root==null){
            return false;
        }
        boolean lSon=dfs(root.left,p,q);//左子树是否包含p或者q
        boolean rSon=dfs(root.right,p,q);//右子树是否包含p或者q
        //如果p和q分别在左右子树中 或者 p(q)是当前节点q(p)在左右子树中 则当前节点就是最低公共祖先
        if ((lSon&&rSon)||((root.val==p.val||root.val==q.val)&&(lSon||rSon))){
            ans=root;
        }
        return lSon||rSon||(root.val==p.val||root.val==q.val);
    }

}


//存储父节点
public class Solution {

    Map<Integer,TreeNode> parent;//祖先集合
    Set<Integer> visited;//以遍历集合

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        parent=new HashMap<>();
        visited=new HashSet<>();
        dfs(root);
        //从p节点开始向上遍历他所有的祖先节点 并加入visited集合
        while (p!=null){
            visited.add(p.val);
            p=parent.get(p.val);//从祖先集合中找到它的父节点
        }
        while (q!=null){
            //如果在以遍历的集合中找到当前节点 则当前节点就是q和p的最低公共祖先
            if (visited.contains(q.val)){
                return q;
            }
            q=parent.get(q.val);
        }
        return null;
    }

    //保存各个节点的父节点
    private void dfs(TreeNode root){
        //当左孩子不为空时 在集合中保存左孩子和他的父节点
        if (root.left!=null){
            parent.put(root.left.val,root);
            dfs(root.left);
        }
        //当右孩子不为空时 在集合中保存右孩子和他的父节点
        if (root.right!=null){
            parent.put(root.right.val,root);
            dfs(root.right);
        }
    }

}

13有序链表转换二叉搜索树(109)

给定一个单链表的头节点 head 其中的元素 按升序排序 将其转换为高度平衡的二叉搜索树。

本题中一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差不超过 1。

输入: head = [-10,-3,0,5,9]
输出: [0,-3,9,-10,null,5]
解释: 一个可能的答案是[0-3,9-10,null,5]它表示所示的高度平衡的二叉搜索树。

输入: head = []
输出: []

//分治
public class Solution {

    public TreeNode sortedListToBST(ListNode head) {
        return buildTree(head,null);
    }

    private TreeNode buildTree(ListNode left, ListNode right) {
        if (left==right){
            return null;
        }
        ListNode mid=getMid(left,right);//得到链表中间的节点
        TreeNode root=new TreeNode(mid.val);//设置当前头节点为mid
        root.left=buildTree(left,mid);//递归重构左子树
        root.right=buildTree(mid.next,right);//递归重构右子树
        return root;
    }

    private ListNode getMid(ListNode left, ListNode right) {
        ListNode slow=left;
        ListNode fast=left;
        while (fast!=right&&fast.next!=right){
            slow=slow.next;//跳一步
            fast=fast.next.next;//跳两步
        }
        return slow;
    }
}

14递增顺序搜索树

给你一棵二叉搜索树的 root 请你 按中序遍历 将其重新排列为一棵递增顺序搜索树使树中最左边的节点成为树的根节点并且每个节点没有左子节点只有一个右子节点。

//保存中序遍历的结果再生成新的树
public class Solution {

    public TreeNode increasingBST(TreeNode root) {
        List<Integer> path=new ArrayList<>();
        dfs(root,path);
        TreeNode newTree=new TreeNode(-1);
        TreeNode curNode=newTree;
        for (int i:path){
            curNode.right=new TreeNode(i);
            curNode=curNode.right;//改变当前节点
        }
        return newTree.right;
    }

    //得到中序遍历序列
    private void dfs(TreeNode root,List<Integer> list){
        if (root==null){
            return;
        }
        dfs(root.left,list);
        list.add(root.val);
        dfs(root.right,list);
    }

}


//在中序遍历时直接生成新的树
public class Solution {

    private TreeNode curNode;

    public TreeNode increasingBST(TreeNode root) {
        TreeNode newTree=new TreeNode(-1);
        curNode=newTree;
        dfs(root);
        return newTree.right;
    }

    //得到中序遍历序列
    private void dfs(TreeNode root){
        if (root==null){
            return;
        }
        dfs(root.left);
        curNode.right=root;//将当前节点的右孩子指向root
        root.left=null;//root的左孩子置为null 因为已经遍历过了
        curNode=root;//修改当前节点
        dfs(root.right);
    }

}

15两数之和 IV - 输入二叉搜索树(653)

给定一个二叉搜索树 root 和一个目标结果 k如果二叉搜索树中存在两个元素且它们的和等于给定的目标结果则返回 true。

输入: root = [5,3,6,2,4,null,7], k = 9
输出: true

输入: root = [5,3,6,2,4,null,7], k = 28
输出: false

//得到中序遍历序列 在中序遍历序列中寻找两数之和为k
public class Solution {

    public boolean findTarget(TreeNode root, int k) {
        List<Integer> path=new ArrayList<>();
        dfs(root,path);
        int left=0;//指向数组的头
        int right=path.size()-1;//指向数组的尾
        while (left<right){
            //当两数之和等于k时 返回true
            if (path.get(left)+ path.get(right)==k){
                return true;
            }
            //当两数之和大于k时 右指针左移
            if (path.get(left)+ path.get(right)>k){
                right--;
            }else {//当两数之和小于k时 右指针右移
                left++;
            }
        }
        return false;
    }

    //得到中序遍历序列
    private void dfs(TreeNode root,List<Integer> list){
        if (root==null){
            return;
        }
        dfs(root.left,list);
        list.add(root.val);
        dfs(root.right,list);
    }

}


//深度优先搜索+哈希表
public class Solution {

    Set<Integer> set=new HashSet<>();

    public boolean findTarget(TreeNode root, int k) {
        if (root==null){
            return false;
        }
        if (set.contains(k- root.val)){
            return true;
        }
        set.add(root.val);
        return findTarget(root.left,k)||findTarget(root.right,k);
    }

}

16 删除二叉搜索树中的节点(450)

给定一个二叉搜索树的根节点 root 和一个值 key删除二叉搜索树中的 key 对应的节点并保证二叉搜索树的性质不变。返回二叉搜索树有可能被更新的根节点的引用。

一般来说删除节点可分为两个步骤

首先找到需要删除的节点
如果找到了删除它。

输入root = [5,3,6,2,4,null,7], key = 3
输出[5,4,6,2,null,null,7]
解释给定需要删除的节点值是 3所以我们首先找到 3 这个节点然后删除它。
一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。
另一个正确答案是 [5,2,6,null,4,null,7]。

输入: root = [], key = 0
输出: []

public class Solution {

    public TreeNode deleteNode(TreeNode root, int key) {
        if (root==null){
            return null;
        }
        //如果当前节点的值大于key 从当前节点的左子树找key
        if (root.val>key){
            root.left=deleteNode(root.left,key);
            return root;
        }
        //如果当前节点的值小于key 从当前节点的右子树找key
        if (root.val<key){
            root.right=deleteNode(root.right,key);
            return root;
        }
        if (root.val==key){
            //当root是叶子节点时 直接删除
            if (root.left==null&&root.right==null){
                return null;
            }
            //当左子树为空 返回右子树
            if (root.left==null){
                return root.right;
            }
            //当右子树为空 返回左子树
            if (root.right==null){
                return root.left;
            }
            //如果左右子树都不为空
            TreeNode node=root.right;//找root的right的最左的那个节点
            while (node.left!=null){
                node=node.left;
            }
            //删除掉root的right的最左的那个节点
            root.right=deleteNode(root.right,node.val);
            //用root的right的最左的那个节点取代root
            node.right=root.right;
            node.left=root.left;
            return node;
        }
        return root;
    }

}