递归算法模板

返回值类型 dfs(参数) {
    if (终止条件) {
        存放结果;
        return 返回值类型;
    }

    每层递归的逻辑
    dfs(下层递归的参数);
}

以下代码绝大多数来自于 代码随想录，代码只为个人学习与总结

二叉树的定义

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;
  	}
}

二叉树的遍历

递归遍历

前序遍历

// 递归·LC144
class Solution {
    ArrayList<Integer> preOrderReverse(TreeNode root) {
        ArrayList<Integer> result = new ArrayList<Integer>();
        preOrder(root, result);
        return result;
    }

    void preOrder(TreeNode root, ArrayList<Integer> result) {
        if (root == null) {
            return;
        }
        result.add(root.val); 
        preOrder(root.left, result);
        preOrder(root.right, result);
    }
}

中序遍历

// 递归·LC94
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        inorder(root, res);
        return res;
    }

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

后序遍历

// 递归·LC145
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        postorder(root, res);
        return res;
    }

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

迭代遍历

前序遍历

// 递归·LC144
// 前序遍历顺序：中-左-右，入栈顺序：中-右-左
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null){
            return result;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()){
            TreeNode node = stack.pop();
            result.add(node.val);
            if (node.right != null){
                stack.push(node.right);
            }
            if (node.left != null){
                stack.push(node.left);
            }
        }
        return result;
    }
}

中序遍历

// 递归·LC94
// 中序遍历顺序: 左-中-右 入栈顺序： 左-右
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null){
            return result;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()){
           if (cur != null){
               stack.push(cur);
               cur = cur.left;
           }else{
               cur = stack.pop();
               result.add(cur.val);
               cur = cur.right;
           }
        }
        return result;
    }
}

后序遍历

// 递归·LC145
// 后序遍历顺序 左-右-中 入栈顺序：中-左-右 出栈顺序：中-右-左， 最后翻转结果
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null){
            return result;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()){
            TreeNode node = stack.pop();
            result.add(node.val);
            if (node.left != null){
                stack.push(node.left);
            }
            if (node.right != null){
                stack.push(node.right);
            }
        }
        Collections.reverse(result);
        return result;
    }
}

统一遍历

迭代法前中后序遍历的统一模板，逻辑相似，只需要修改代码的顺序。

前序遍历

// 递归·LC144
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new LinkedList<>();
        Stack<TreeNode> st = new Stack<>();
        if (root != null) st.push(root);
        while (!st.empty()) {
            TreeNode node = st.peek();
            if (node != null) {
                st.pop(); // 将该节点弹出，避免重复操作，下面再将右中左节点添加到栈中
                if (node.right!=null) st.push(node.right);  // 添加右节点（空节点不入栈）
                if (node.left!=null) st.push(node.left);    // 添加左节点（空节点不入栈）
                st.push(node);                          // 添加中节点
                st.push(null); // 中节点访问过，但是还没有处理，加入空节点做为标记。
                
            } else { // 只有遇到空节点的时候，才将下一个节点放进结果集
                st.pop();           // 将空节点弹出
                node = st.peek();    // 重新取出栈中元素
                st.pop();
                result.add(node.val); // 加入到结果集
            }
        }
        return result;
    }
}

中序遍历

// 递归·LC94
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new LinkedList<>();
    Stack<TreeNode> st = new Stack<>();
    if (root != null) st.push(root);
    while (!st.empty()) {
        TreeNode node = st.peek();
        if (node != null) {
            st.pop(); // 将该节点弹出，避免重复操作，下面再将右中左节点添加到栈中
            if (node.right!=null) st.push(node.right);  // 添加右节点（空节点不入栈）
            st.push(node);                          // 添加中节点
            st.push(null); // 中节点访问过，但是还没有处理，加入空节点做为标记。

            if (node.left!=null) st.push(node.left);    // 添加左节点（空节点不入栈）
        } else { // 只有遇到空节点的时候，才将下一个节点放进结果集
            st.pop();           // 将空节点弹出
            node = st.peek();    // 重新取出栈中元素
            st.pop();
            result.add(node.val); // 加入到结果集
        }
    }
    return result;
}
}

后序遍历

// 递归·LC145
class Solution {
   public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new LinkedList<>();
        Stack<TreeNode> st = new Stack<>();
        if (root != null) st.push(root);
        while (!st.empty()) {
            TreeNode node = st.peek();
            if (node != null) {
                st.pop(); // 将该节点弹出，避免重复操作，下面再将右中左节点添加到栈中
                st.push(node);                          // 添加中节点
                st.push(null); // 中节点访问过，但是还没有处理，加入空节点做为标记。
                if (node.right!=null) st.push(node.right);  // 添加右节点（空节点不入栈）
                if (node.left!=null) st.push(node.left);    // 添加左节点（空节点不入栈）         
                               
            } else { // 只有遇到空节点的时候，才将下一个节点放进结果集
                st.pop();           // 将空节点弹出
                node = st.peek();    // 重新取出栈中元素
                st.pop();
                result.add(node.val); // 加入到结果集
            }
        }
        return result;
   }
}

层序遍历

层序遍历模板

// 102.二叉树的层序遍历
class Solution {
    public List<List<Integer>> resList = new ArrayList<List<Integer>>();

    public List<List<Integer>> levelOrder(TreeNode root) {
        //checkFun01(root,0);
        checkFun02(root);

        return resList;
    }

    //DFS--递归方式
    public void checkFun01(TreeNode node, Integer deep) {
        if (node == null) return;
        deep++;

        if (resList.size() < deep) {
            //当层级增加时，list的Item也增加，利用list的索引值进行层级界定
            List<Integer> item = new ArrayList<Integer>();
            resList.add(item);
        }
        resList.get(deep - 1).add(node.val);

        checkFun01(node.left, deep);
        checkFun01(node.right, deep);
    }

    //BFS--迭代方式--借助队列
    public void checkFun02(TreeNode node) {
        if (node == null) return;
        Queue<TreeNode> que = new LinkedList<TreeNode>();
        que.offer(node);

        while (!que.isEmpty()) {
            List<Integer> itemList = new ArrayList<Integer>();
            int len = que.size();

            while (len > 0) {
                TreeNode tmpNode = que.poll();
                itemList.add(tmpNode.val);

                if (tmpNode.left != null) que.offer(tmpNode.left);
                if (tmpNode.right != null) que.offer(tmpNode.right);
                len--;
            }

            resList.add(itemList);
        }

    }
}

翻转二叉树

//DFS递归
class Solution {
   /**
     * 前后序遍历都可以
     * 中序不行，因为先左孩子交换孩子，再根交换孩子（做完后，右孩子已经变成了原来的左孩子），再右孩子交换孩子（此时其实是对原来的左孩子做交换）
     */
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        invertTree(root.left);
        invertTree(root.right);
        swapChildren(root);
        return root;
    }

    private void swapChildren(TreeNode root) {
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
    }
}

//BFS
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {return null;}
        ArrayDeque<TreeNode> deque = new ArrayDeque<>();
        deque.offer(root);
        while (!deque.isEmpty()) {
            int size = deque.size();
            while (size-- > 0) {
                TreeNode node = deque.poll();
                swap(node);
                if (node.left != null) {deque.offer(node.left);}
                if (node.right != null) {deque.offer(node.right);}
            }
        }
        return root;
    }

    public void swap(TreeNode root) {
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
    }
}

对称二叉树

以二叉树的遍历为基础，只是处理节点的顺序从两侧外开始逐渐靠内。主要难点在于确定所有不对称的条件。

递归法

class Solution {
    public boolean isSymmetric(TreeNode root) {
        return compare(root.left,root.right);
    }
    public boolean compare(TreeNode left,TreeNode right){
        //循环终止条件为两节点不对称以及两节点为空
        if(left==null&&right==null){
            return true;
        }
        if(left==null && right!=null){
            return false;
        }
        if(left!=null && right==null){
            return false;
        }
        if(left.val!=right.val){
            return false;
        }
       
        boolean outside= compare(left.left,right.right);
        boolean inside= compare(left.right,right.left);
        //外侧内侧皆相同即true
        return outside && inside;
    }
}

迭代法

与层序遍历不同，判断对称并不需要确定节点属于哪一层，只要按一定顺序将它们输入队列即可。

class Solution {
    public boolean isSymmetric(TreeNode root) {
        Queue<TreeNode> que=new LinkedList<>();
        que.offer(root.left);
        que.offer(root.right);
        while(!que.isEmpty()){
            TreeNode left=que.poll();
            TreeNode right=que.poll();
            if(left==null && right==null){//左右节点为空时对称
                continue;
            }
            //左右节点只有一个为0，或者左右节点值不相同则不对称
            if(left==null || right==null || left.val!=right.val){
                return false;
            }
         
            que.offer(left.left);
            que.offer(right.right);
            que.offer(left.right);
            que.offer(right.left);
        }
        return true;
    }
}

二叉树的最大深度

递归法

//前序遍历 递归求深度
class Solution {
    public int maxDepth(TreeNode root) {
        if(root==null){return 0;}
        int left=maxDepth(root.left);
        int right=maxDepth(root.right);
        return Math.max(left,right)+1;
    }
}

迭代法

class Solution {
    public int maxDepth(TreeNode root) {
       if(root==null){
           return 0;
       }
       Queue<TreeNode> que=new LinkedList<>();
       que.offer(root);
       int depth=0;
       while(!que.isEmpty()){
           int size=que.size();
           depth++;
           while(size>0){
               TreeNode poll=que.poll();
               if(poll.left!=null){
                   que.offer(poll.left);
               }
               if(poll.right!=null){
                   que.offer(poll.right);
               }
               size--;
           }
       }
       return depth;
    }
}

二叉树的最小深度

递归法

与最大深度类似，但要注意最小深度是从根节点到最近叶子节点的最短路径上的节点数量。没有子节点才是叶子节点，遍历到某个只有一个子节点的节点可能会错误判断

//为了找到没有子节点的节点，这里对只有一个子节点的节点进行判断
class Solution {
public:
    int minDepth(TreeNode* root) {
        if(root==null){
            return 0;
        }
        int left=minDepth(root.left);
        int right=minDepth(root.right);
        if(root.left==null){return right+1;}
        if(root.right==null){return left+1;}
        return Math.min(left,right)+1;
    }
};

迭代法

//深度理解为层序遍历的层数
class Solution {
    public int minDepth(TreeNode root) {

       if(root==null){
           return 0;
       }
       Queue<TreeNode> que=new LinkedList<>();
       que.offer(root);
       int depth=0;
       while(!que.isEmpty()){
           int size=que.size();
           depth++;
           while(size>0){
               TreeNode poll=que.poll();
	//poll为叶子节点则返回深度
               if(poll.left==null && poll.right==null){
                   return depth;
               }
               if(poll.left!=null){
                   que.offer(poll.left);
               }
               if(poll.right!=null){
                   que.offer(poll.right);
               }
               size--;
           }
       }
       return depth;
    }
}

完全二叉树的最小个数

递归法

class Solution {
    public int countNodes(TreeNode root) {
        if(root==null){
            return 0;
        }
        int left=countNodes(root.left);
        int right=countNodes(root.right);
        return left+right+1;
    }
}

完全二叉树的做法

class Solution {
    /**
     * 满二叉树的结点数为：2^depth - 1
     */
    public int countNodes(TreeNode root) {
        if(root == null) {
            return 0;
        }
        int leftDepth = getDepth(root.left);
        int rightDepth = getDepth(root.right);
        if (leftDepth == rightDepth) {// 左子树是满二叉树
            // 2^leftDepth其实是 （2^leftDepth - 1） + 1 ，左子树 + 根结点
            return (1 << leftDepth) + countNodes(root.right);
        } else {// 右子树是满二叉树
            return (1 << rightDepth) + countNodes(root.left);
        }
    }

    private int getDepth(TreeNode root) {
        int depth = 0;
        while (root != null) {
            root = root.left;
            depth++;
        }
        return depth;
    }
}

判断是否为平衡二叉树

递归法

class Solution {
    public boolean isBalanced(TreeNode root) {
        return getDepth(root)!=-1;
    }
//不为平衡二叉树返回-1
    public int getDepth(TreeNode node){
        if(node==null){
            return 1;
        }
        int left=getDepth(node.left);
        if(left==-1){
            return -1;
        }
        int right=getDepth(node.right);
        if(right==-1){
            return -1;
        }

        if(Math.abs(left-right)>1){
            return -1;
        }else{
            return Math.max(left,right)+1;
        }
    }
}

查找二叉树的所有路径

递归法

思路是递归回溯，每一次回溯之后删除末尾节点有些像全排列的感觉

class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> res=new ArrayList<>();
        if(res==null){
            return res;
        }
        List<Integer> path =new ArrayList<>();
        dfs(root,path,res);
        return res;
    }
    public void dfs(TreeNode node,List<Integer> path ,List<String> res){
        path.add(node.val);
        StringBuilder sb=new StringBuilder();
        if(node.left==null && node.right==null){
            for(int i=0;i<path.size()-1;i++){
                sb.append(path.get(i)).append("->");
            }
            sb.append(path.get(path.size()-1));
            res.add(sb.toString());
            return ;
        }
        if(node.left!=null){
            dfs(node.left,path,res);
            path.remove(path.size()-1);//删除末位节点
        }
        if(node.right!=null){
            dfs(node.right,path,res);
            path.remove(path.size()-1);
        }
    }
}

二叉树的左叶子节点之和

递归法

左叶子节点的判断方法是，该节点是父节点的左节点，且该节点没有子节点。
根据二叉树的特点，指针指在子节点时是无法回到父节点判断自己是否为左子节点，所以要从父节点就开始判断它的左子节点是否为叶子节点。

class Solution {
    public int sumOfLeftLeaves(TreeNode root) {
        if(root==null){
            return 0;
        }
        int left=sumOfLeftLeaves(root.left);
        int right=sumOfLeftLeaves(root.right);

        int count=0;
        if(root.left!=null && root.left.left==null && root.left.right==null){
            count=root.left.val;
        }
        return left+right+count;
    }
}

迭代法

class Solution {
    public int sumOfLeftLeaves(TreeNode root) {
        if(root==null){
            return 0;
        }
        Stack<TreeNode> st=new Stack<>();
        st.add(root);
        int sum=0;
        while(!st.isEmpty()){
            TreeNode node=st.pop();
            if(node.left!=null && node.left.left==null && node.left.right==null){
                sum+=node.left.val;   
            }
            if(node.left!=null){st.add(node.left);}
            if(node.right!=null){st.add(node.right);}

        }
        return sum;
    }
}

找树左下角的值

迭代法

设法找到最后一层的第一个节点，修改一下层序遍历即可。

class Solution {
    public int findBottomLeftValue(TreeNode root) {
        Queue<TreeNode> que=new LinkedList<>();
        que.offer(root);
        int first=0;
        while(!que.isEmpty()){
            int size=que.size();
            for(int i=0;i<size;i++){
                TreeNode node=que.poll();
                if(i==0){first=node.val;}
                if(node.left!=null){que.offer(node.left);}
                if(node.right!=null){que.offer(node.right);}

            }
        }
        return first;
    }
}

二叉树的路径总和

class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if(root==null){
            return false;
        }
        targetSum-=root.val;
        if(root.left==null && root.right==null){
            if(targetSum==0){
                return true;
            }
        }
        if(root.left!=null){
            boolean left=hasPathSum(root.left,targetSum);
            if(left){
                return true;
            }
        }

        if(root.right!=null){
            boolean right=hasPathSum(root.right,targetSum);
            if(right){
                return true;
            }
        }
        return false;
    }
}

路径总和II

class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<List<Integer>> res=new ArrayList<>();
        if(root==null){return res;}

        List<Integer> path=new LinkedList<>();
        dfs(root,targetSum,res,path);
        return res;
    }
    public void dfs(TreeNode root,int targetSum,List<List<Integer>> res,List<Integer> path){
        path.add(root.val);
        if(root.left==null && root.right==null && targetSum==root.val){
            res.add(new ArrayList<>(path));
        
        return ;//和不为targetSum,返回
        }
        if(root.left!=null){
        dfs(root.left,targetSum-root.val,res,path);
        path.remove(path.size()-1);
        }
        if(root.right!=null){
            dfs(root.right,targetSum-root.val,res,path);
            path.remove(path.size()-1);
        }
    } 
    
}

从中序与后序遍历序列构造二叉树

通过后序序列的最后一个节点值得到根节点，之后通过它在中序遍历中切割左右子树的中序与后序遍历，在通过递归再次找子树的结构。
易错点是，左右子树的区间的端点控制。

class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        return buildTree1(inorder,0,inorder.length,postorder,0,postorder.length);
    }
    public TreeNode buildTree1(int[] inorder,int inLeft,int inRight,int[] postorder, int postLeft,int postRight){
                                    if(inRight-inLeft<1){
                                        return null;
                                    }
                                    if(inRight-inLeft==1){
                                        return new TreeNode(inorder[inLeft]);
                                    }
                                    int rootVal=postorder[postRight-1];
                                    TreeNode root=new TreeNode(rootVal);

                                    int rootIndex=0;
                                    for(rootIndex=inLeft;rootIndex<inRight;rootIndex++){
                                        if(inorder[rootIndex]==rootVal){
                                            break;
                                        }
                                    }

                                    root.left=buildTree1(inorder,inLeft,rootIndex,postorder,postLeft,postLeft+(rootIndex-inLeft));

                                    root.right=buildTree1(inorder,rootIndex+1,inRight,postorder,postLeft+(rootIndex-inLeft),postRight-1);
                                    return root;
    }
}

构造最大二叉树

留意区间边界

//LC654
class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return dfs(nums,0,nums.length);
    }
    
    public TreeNode dfs(int[] nums,int l,int r){
        if(r-l<1){
            return null;
        }

        if(r-l==1){
            TreeNode node=new TreeNode(nums[l]);
            return node;
        }
        int maxIndex=l;
        int maxVal=nums[l];
        for(int i=l+1;i<r;i++){
            if(nums[i]>maxVal){
                maxVal=nums[i];
                maxIndex=i;
            }
        }
        TreeNode root=new TreeNode(maxVal);

        root.left=dfs(nums,l,maxIndex);
        root.right=dfs(nums,maxIndex+1,r);

        return root;
    }
}

合并二叉树

迭代法

就像迭代法遍历树，这次同时遍历两个树，注意这次的递归终止条件，因为要合并树，那么就有两个树遍历的节点t1 和 t2，如果t1 == NULL 了，两个树合并就应该是 t2 了啊（如果t2也为NULL也无所谓，合并之后就是NULL）。反过来如果t2 == NULL，那么两个数合并就是t1（如果t1也为NULL也无所谓，合并之后就是NULL）。

class Solution {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if(root1==null){return root2;}
        if(root2==null){return root1;}

        root1.val+=root2.val;
        root1.left=mergeTrees(root1.left,root2.left);
        root1.right=mergeTrees(root1.right,root2.right);
        return root1;
    }
}

搜索二叉搜索树

递归法

二叉搜索树是一个有序树：

若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
它的左、右子树也分别为二叉搜索树

//CL700
class Solution {
public TreeNode searchBST(TreeNode root, int val) {
        if(root==null || root.val==val){return root;}

        if(val < root.val){
            return searchBST(root.left,val);
        }else{
            return searchBST(root.right,val);
        }       
    }
}

迭代法

由于搜索树的特点，搜索时有了方向，不要用栈把所有节点遍历。

class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        while(root!=null){
            if(val<root.val){
                root=root.left;
            }else if(val>root.val){
                root=root.right;
            }else{
                return root;
            }
        }
        return root;
    }
}

验证二叉搜索树

这里注意不能单纯的比较左节点小于中间节点，右节点大于中间节点就完事了。
我们要比较的是左子树所有节点小于中间节点，右子树所有节点大于中间节点。

递归法

class Solution {
    TreeNode max;
    public boolean isValidBST(TreeNode root) {
        if(root==null)return true;

        boolean left=isValidBST(root.left);
        if(!left){
            return false;
        }
        //max不为空时，它的值是此次递归的根节点的左子节点，也是上次递归的根节点
        if(max!=null && root.val<=max.val){
            return false;
        }

        max=root;

        boolean right=isValidBST(root.right);
        return right;
    }
}

二叉搜索树的最小绝对差

递归法

由于二叉搜索树的性质，本质上还是中序遍历，同样迭代法也是在中序遍历的迭代版本，这里就不写了。

 //LC530
class Solution {
    int res=Integer.MAX_VALUE;
    TreeNode pre;
    public int getMinimumDifference(TreeNode root) {
        if(root==null){return 0;}

        if(root.left!=null){
            getMinimumDifference(root.left);
        }

        if(pre!=null){
            res=Math.min(res,root.val-pre.val);
        }
        pre=root;

        if(root.right!=null){
            getMinimumDifference(root.right);
        }

        return res;
    }
}

二叉搜索树的众数

递归法

 //LC501
class Solution {
    List<Integer> list=new ArrayList<>();
    int maxcount=0;
    int count=0;
    TreeNode pre;
    public int[] findMode(TreeNode root) {
        dfs(root);
        int[] res=new int[list.size()];
        //注意i要在循环外声明
        int i=0;
        for(int item:list){
            res[i++]=item;
        }
        return res;
    }

    public void dfs(TreeNode root){
        if(root==null){
            return;
        }

        dfs(root.left);
        //中序遍历时，都要考虑pre节点是否为空。
        if(pre==null || pre.val!=root.val){
            count=1;
        }else{
            count++;
        }
        //更新maxcount，如果count较大说明之前录入的不为众数。之前的数据要清空
        if(count>maxcount){
            maxcount=count;
            list.clear();
            list.add(root.val);
        }else if(count==maxcount){
            list.add(root.val);
        }
        pre=root;
        dfs(root.right);
    }
}

普通二叉树求众数

class Solution {
	public int[] findMode(FindModeInBinarySearchTree.TreeNode root) {
		Map<Integer, Integer> map = new HashMap<>();
		List<Integer> list = new ArrayList<>();
		if (root == null) return list.stream().mapToInt(Integer::intValue).toArray();
		// 获得频率 Map
		searchBST(root, map);
		List<Map.Entry<Integer, Integer>> mapList = map.entrySet().stream()
				.sorted((c1, c2) -> c2.getValue().compareTo(c1.getValue()))
				.collect(Collectors.toList());
		list.add(mapList.get(0).getKey());
		// 把频率最高的加入 list
		for (int i = 1; i < mapList.size(); i++) {
			if (mapList.get(i).getValue() == mapList.get(i - 1).getValue()) {
				list.add(mapList.get(i).getKey());
			} else {
				break;
			}
		}
		return list.stream().mapToInt(Integer::intValue).toArray();
	}

	void searchBST(FindModeInBinarySearchTree.TreeNode curr, Map<Integer, Integer> map) {
		if (curr == null) return;
		map.put(curr.val, map.getOrDefault(curr.val, 0) + 1);
		searchBST(curr.left, map);
		searchBST(curr.right, map);
	}

}

求二叉树的最近公共祖先

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
需要注意的是：

求最小公共祖先，需要从底向上遍历，那么二叉树，只能通过后序遍历（即：回溯）实现从低向上的遍历方式。
在回溯的过程中，必然要遍历整颗二叉树，即使已经找到结果了，依然要把其他节点遍历完，因为要使用递归函数的返回值（也就是代码中的left和right）做逻辑判断。

要理解如果返回值left为空，right不为空为什么要返回right，为什么可以用返回right传给上一层结果。

//LC236
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        return dfs(root,p,q);
    }
    public TreeNode dfs(TreeNode root,TreeNode p,TreeNode q){
        //如果某条路线没有找到p或q，到叶子节点后就会向上返回null
        if(root==null || root==p || root==q){
            return root;
        }
        //后序遍历
        TreeNode left=dfs(root.left,p,q);
        TreeNode right=dfs(root.right,p,q);
        //不为null就为目标结点，此时的root就为公共祖先
        if(left!=null && right!=null){
            return root;
        }
        //也有可能目标节点都在目前根节点的右子树，当然此次回溯的节点必不为所求得公共祖先了，反之亦然。
        if(left==null){
            return right;
        }
        return left;
    }
}

二叉搜索树的公共祖先

//LC235
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        while(true){
            if(root.val>p.val && root.val>q.val){
                root=root.left;
            }else if(root.val<p.val && root.val<q.val){
                root=root.right;
            }else{
                break;
            }
        }
        return root;
    }
}

在二叉搜索树中插入节点

 //LC701
class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        //为空节点时插入
        if(root==null){
            TreeNode node=new TreeNode(val);
            return node;
        }
        
        //通过回溯阶段完成了新加入节点的父子关系赋值操作了，下一层将加入节点返回，本层用root.left或者root.right将其接住。
        if(val<root.val){root.left=insertIntoBST(root.left,val);}
        if(val>root.val){root.right=insertIntoBST(root.right,val);}
        return root;
    }
}

删除二树的特定节点

删除二叉搜索树的特定节点

删除特定节点必须要改变二叉树结构，有以下五种情况：

第一种情况：没找到删除的节点，遍历到空节点直接返回了

找到删除的节点
** 第二种情况：左右孩子都为空（叶子节点），直接删除节点，返回NULL为根节点
** 第三种情况：删除节点的左孩子为空，右孩子不为空，删除节点，右孩子补位，返回右孩子为根节点
** 第四种情况：删除节点的右孩子为空，左孩子不为空，删除节点，左孩子补位，返回左孩子为根节点
** 第五种情况：左右孩子节点都不为空，则将删除节点的左子树头结点（左孩子）放到删除节点的右子树的最左面节点的左孩子上，返回删除节点右孩子为新的根节点。

 //LC450
class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        //没有找到节点
        if(root==null){
            return null;
        }
        //找到了目标节点
        if(root.val==key){
            if(root.right==null){return root.left;}
            else if(root.left==null){return root.right;}
            //目标节点左右节点都不为空
            else{
                //找到目标节点的右子树的最左侧叶子节点，其最小
                TreeNode temp=root.right;
                while(temp.left!=null){
                    temp=temp.left;
                }
                //最左侧叶子节点指向目标节点的左子树，则仍然为二叉搜索树
                temp.left=root.left;
                //删除目标节点
                root=root.right;
                return root;
            }
        }
        
        if(root.left!=null){root.left=deleteNode(root.left,key);}
        if(root.right!=null){root.right=deleteNode(root.right,key);}
        return root;
    }
}

删除二叉树的特定节点

//C++代码
class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        if (root == nullptr) return root;
        if (root->val == key) {
            if (root->right == nullptr) { // 这里第二次操作目标值：最终删除的作用
                return root->left;
            }
            TreeNode *cur = root->right;
            while (cur->left) {
                cur = cur->left;
            }
            swap(root->val, cur->val); // 这里第一次操作目标值：交换目标值其右子树最左面节点。
        }
        root->left = deleteNode(root->left, key);
        root->right = deleteNode(root->right, key);
        return root;
    }
};

修剪二叉搜索树

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

        if(root.val<low){//此时没有必要遍历左子树了
            //新建一个节点来存root的右子树，之后返回这个节点，这个过程中，root被架空了
            TreeNode right=trimBST(root.right,low,high);
            return right;
        }

        if(root.val>high){//此时没有必要遍历右子树了
            TreeNode left=trimBST(root.left,low,high);
            return left;
        }

        if(root.left!=null){root.left=trimBST(root.left,low,high);}
        if(root.right!=null){root.right=trimBST(root.right,low,high);}
        return root;
    }
}

将有序数组转换为二叉搜索树

 //LC108
class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return dfs(nums,0,nums.length);
    }
    public TreeNode dfs(int[] nums,int left,int right){
        if(left>=right){
            return null;
        }

        if(right-left==1){
            return new TreeNode(nums[left]);
        }
        int mid=left+(right-left)/2;
        TreeNode root=new TreeNode(nums[mid]);
        root.left=dfs(nums,left,mid);
        root.right=dfs(nums,mid+1,right);
        return root;
    }
}

将二叉搜索树转化为累加树

 //LC538
class Solution {
    int pre=0;
    public TreeNode convertBST(TreeNode root) {
        dfs(root);
        return root;
    }
    public void dfs(TreeNode root){
        if(root==null){return;}
        dfs(root.right);
        root.val+=pre;
        pre=root.val;
        dfs(root.left);
    }
}