深度

104. 二叉树的最大深度

https://leetcode.cn/problems/maximum-depth-of-binary-tree/
求深度用前序遍历

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

111.二叉树的最小深度

https://leetcode.cn/problems/minimum-depth-of-binary-tree/description/
求高度用后序遍历

class Solution {
    public int minDepth(TreeNode root) {
        if(root == null) return 0;
        int l = minDepth(root.left);
        int r = minDepth(root.right);

        int min = 0;
        if(root.left != null && root.right != null) min = Math.min(l, r);
        if(root.left == null) min = r;
        if(root.right == null) min = l;

        return min + 1;
    }
}

110. 平衡二叉树

https://leetcode.cn/problems/balanced-binary-tree/

左子树的高度和右子树的高度相差小于1，如何返回左右最高的深度+1，否则直接返回负数

class Solution {
    public boolean isBalanced(TreeNode root) {
        return dfs(root) >= 0 ? true : false;
    }

    public int dfs(TreeNode root) {
        if(root == null) return 0;

        int deepL = dfs(root.left);
        int deepR = dfs(root.right);
        if(deepL < 0 || deepR < 0) return -5;

        if(Math.abs(deepL - deepR) > 1) return -5;
        else return Math.max(deepL, deepR) + 1;
    }
}

叶子节点

112.路径总和

https://leetcode.cn/problems/path-sum/description/?orderBy=newest_to_oldest

注意题目要求的叶子节点，一般有这种条件的都需要判断左右节点为空。

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

404. 左叶子之和

要从父节点去判断左子节点是否为叶子节点

class Solution {
    public int sumOfLeftLeaves(TreeNode root) {

        if(root == null) return 0;

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

        int numL = sumOfLeftLeaves(root.left);
        int numR = sumOfLeftLeaves(root.right);

        return numL + numR + num;
    }
}

513.找树左下角的值

https://leetcode.cn/problems/find-bottom-left-tree-value/description/

BFS层序遍历，将每层遍历结果放入一个list中最后一层的list的第一个值就是结果

class Solution {
    Deque<TreeNode> deque = new LinkedList<>(); 

    public int findBottomLeftValue(TreeNode root) {
        int res = 0;
        deque.addLast(root);

        while(deque.size() != 0){
            int size = deque.size();
            ArrayList<Integer> list = new ArrayList<>();

            for(int i = 0; i < size; i++) {
                TreeNode node = deque.removeFirst();
                list.add(node.val);

                if(node.left != null) deque.addLast(node.left);
                if(node.right != null) deque.addLast(node.right);
            }
            if(list.size() != 0) res = list.get(0);
        }
        return res;
    }
}

构建二叉树

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

https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/description/

现将中序数组存入哈希表中，key为值， value为下表，目的是为了根据后序数组的最后一个根节点的值找到前序数组根节点的位置，

然后根据中序数组，计算出两个数组左右两个子树的数组区间，递归

inL idx inR
9 ==3== 15 20 7 poL –> idx-1 pol –> idx - inL + poL - 1

9 15 7 20 ==3== idx + 1 –> inR idx - inL + poL - 1 –> poR - 1
poL poR

class Solution {
    HashMap<Integer,Integer> map = new HashMap<>();

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        for(int i = 0; i <= inorder.length-1; i++) {
            map.put(inorder[i], i);
        }
        return dfs(inorder, postorder, 0, inorder.length-1, 0, postorder.length-1);
    }

    public TreeNode dfs(int[] inorder, int[] postorder, int inL, int inR, int poL, int poR) {
        if(poL > poR) return null;

        int rootVal = postorder[poR];
        TreeNode root = new TreeNode(rootVal);

        int idx = map.get(rootVal);

        root.left = dfs(inorder, postorder, inL, idx-1, poL, idx - inL - 1 + poL);
        root.right = dfs(inorder, postorder, idx + 1, inR, idx - inL + poL, poR - 1);
        return root;
    }
}

654. 最大二叉树

https://leetcode.cn/problems/maximum-binary-tree/description/
和上一题类似
根据区间，L、R 遍历找出最大值的数组下标
然后再根据下标进行分割区间

class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return dfs(nums, 0, nums.length-1);
    }

    public TreeNode dfs(int[] nums, int L, int R) {
        if(L > R) return null;

        int idx = L;
        int max = nums[L];
        for(int i = L+1; i <= R; i++) {
            if(nums[i] > max) {
                max = nums[i];
                idx = i;
            }
        }
        TreeNode root = new TreeNode(nums[idx]);

        root.left = dfs(nums, L, idx - 1);
        root.right = dfs(nums, idx + 1, R);
        return root;
    }
}

时间复杂度：O(n^2)，n 是数组的长度。
在最坏的情况下，数组严格递增或递减，需要递归n层，第 i层需要遍历 n−i 个元素以找出最大值，总时间复杂度为 O(n^2)

617. 合并二叉树

https://leetcode.cn/problems/merge-two-binary-trees/description/
当一个节点为空时，直接返回另一个节点就可以了，并终止当前子树的深搜

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

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

二叉搜索树

98.验证二叉搜索树

https://leetcode.cn/problems/validate-binary-search-tree/description/
中序遍历，只要当前节点大于上一个节点pre就true
遍历到当前节点就进行判断是否符合大于上个节点，如果符合就讲当前节点作为上个节点

class Solution {
    TreeNode pre;

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

        if(!isValidBST(root.left)) return false;

        if(pre != null && root.val <= pre.val)  return false;
        pre = root;

        return isValidBST(root.right);
    }
}

530. 二叉搜索树的最小绝对差

https://leetcode.cn/problems/minimum-absolute-difference-in-bst/
和上一题一样，利用二叉搜索树的特性，中序遍历，使当前节点进去上个节点，比较差值，最小的就是答案。
minL左子树最小差值
min 当前节点和上个节点的差值与minL 的最小差值
minR左子树最小差值

return minR和min 中的最小值

class Solution {
    int pre = -1;
    int min = Integer.MAX_VALUE;
    public int getMinimumDifference(TreeNode root) {
        if(root == null) return Integer.MAX_VALUE;

        int minL = getMinimumDifference(root.left);

        if(pre > -1) min = Math.min((root.val - pre), min);
        pre = root.val;

        int minR = getMinimumDifference(root.right);

        return Math.min(minR, min);
    }
}

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

https://leetcode.cn/problems/convert-sorted-array-to-binary-search-tree/description/
二分就行了

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return dfs(nums, 0, nums.length-1);
    }

    public TreeNode dfs(int[] nums, int l, int r) {
        if(l > r) return null;

        int mid = l + (r - l) / 2;
        TreeNode root = new TreeNode(nums[mid]);
        
        root.left = dfs(nums, l, mid - 1);
        root.right = dfs(nums, mid + 1, r);

        return root;
    }
}

501. 二叉搜索树中的众数

方法一：暴力

中序遍历，将结果存入map中 key为节点值， value为出现次数
然后在遍历map 并进行比较处理
如果 value大于max 就将栈清空，并将该key存入栈中
如果一样，就将key加入栈中
最后将结果存入数组中

class Solution {

    HashMap<Integer, Integer> map = new HashMap<>();
    Deque<Integer> deque = new LinkedList<>(); 
    int maxV = -1;

    public int[] findMode(TreeNode root) {
        dfs(root);

        Set entrySet = map.entrySet();
        Iterator iterator =  entrySet.iterator();
        while(iterator.hasNext()) {
            Map.Entry entry = (Map.Entry)iterator.next();
            int key = (int)entry.getKey();
            int value = (int)entry.getValue();

            if(value == maxV) deque.addLast(key);
            if(value > maxV){
                deque.clear();
                deque.addLast(key);
                maxV = value;
            }
        }

        int size = deque.size();
        int[] res = new int[size];
        for(int i = 0; i <= size-1; i++) {
            res[i] = deque.removeFirst();
        }
        return res;

    }

    public void dfs(TreeNode root) {
        if(root == null) return;
        dfs(root.left);
        map.put(root.val, map.getOrDefault(root.val, 0) + 1);
        dfs(root.right);
    }
}

方法二：利用搜索树特性
直接在中序遍历中进行栈的操作，
先将遍历到的节点进行计数count
如果count大于maxC 就将栈清空并将当前的节点值放入
如果等于就加入栈中，
如果小于就跳过
最后当前节点设为上个节点

最后将栈中的元素输出到数组中返回

class Solution {

    Deque<Integer> deque = new LinkedList<>(); 
    int maxC = -1;
    int count = 0;
    TreeNode pre;

    public int[] findMode(TreeNode root) {
        dfs(root);

        int size = deque.size();
        int[] res = new int[size];
        for(int i = 0; i <= size-1; i++) {
            res[i] = deque.removeFirst();
        }
        return res;

    }

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

        if(pre == null || root.val !=  pre.val) count = 1;
        else count++;

        if(count > maxC) {
            deque.clear();
            deque.addLast(root.val);
            maxC = count;
        }else if(count == maxC) {
            deque.addLast(root.val);
        }
        pre = root;

        dfs(root.right);
    }
}

701. 二叉搜索树中的插入操作

https://leetcode.cn/problems/insert-into-a-binary-search-tree/description/

如果val大于当前节点就向右子树递归反之向左子树
如果当前节点为null 就创建节点返回将新节点连接到当前位置
最后返回根节点

class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if(root == null) return new TreeNode(val);

        if(val > root.val) root.right = insertIntoBST(root.right, val);
        else root.left = insertIntoBST(root.left, val);
        
        return root;
    }
}

450. 删除二叉搜索树中的节点

https://leetcode.cn/problems/delete-node-in-a-bst/

找到目标节点
将该节点替换为左子节点
将该节点的右子节点向右子节点的右子树递归直到为null 然后连接

class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        if(root == null) return null;

        if(root.val > key) root.left = deleteNode(root.left, key);
        else if(root.val < key) root.right = deleteNode(root.right, key); 
        else {
            if(root.left == null || root.right == null) {
                root = root.left == null ? root.right : root.left;
                return root;
            }

            TreeNode tempR = root.right;
            root = root.left;

            TreeNode temp = root;
            while(temp.right != null) {
                temp = temp.right;
            }
            temp.right = tempR;
        }
        return root;
    }
}

669. 修剪二叉搜索树

https://leetcode.cn/problems/trim-a-binary-search-tree/description/?orderBy=newest_to_oldest
遍历
如果当前节点的值小于左区间那么当前节点和左子树肯定不符合要求就去判断右子树返回符合的节点
如果当前节点的值大于右区间那么当前节点和右子树肯定不符合要求就去判断左子树返回符合的节点
如果当前节点的值在区间里就递归左右子树连接符合要求的左右子树

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

        if(root.val < low) return trimBST(root.right, low, high);
        if(root.val > high) return trimBST(root.left, low, high);

        root.left = trimBST(root.left, low, high);
        root.right = trimBST(root.right, low, high);
        
        return root;
    }
}

538. 把二叉搜索树转换为累加树

https://leetcode.cn/problems/convert-bst-to-greater-tree/description/
累加树就是当前节点的值为这棵树上** 比当前节点值大的节点值之和**
又题目中是二叉搜索树所以最右边的节点没有比他大的节点，所以还是他自己本身，而的比该节点的父节点大的节点只有他所以使用**反向中序遍历二叉搜索树 ** 就行了

class Solution {
    int pre = 0;
    public TreeNode convertBST(TreeNode root) {
        dfs(root);
        return root;
    }

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

        convertBST(root.right);

        root.val = pre + root.val;
        pre = root.val;

        convertBST(root.left);
    }
}

公共祖先

236. 二叉树的最近公共祖先

https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/description/
需要重下往上找使用后序遍历
如果当前节点的左右子树都找到了目标节点，说明该节点是最近公共祖先返回该节点
如果当前节点就是目标节点，就返回该节点

最后向上返回左子树已找到的节点或者右子树已找到的节点（如果都没有找到就返回null）

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null) return null;

        TreeNode L = lowestCommonAncestor(root.left, p, q);
        TreeNode R = lowestCommonAncestor(root.right, p, q);

        if((L != null && R != null) || root == p || root == q) return root;
        return L == null ? R : L;
    }
}

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

https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-search-tree/description/
根据二叉搜索树的性质
如果该节点大于p、q 那么该节点就是最近公共祖先
否则就根据当前节点的是否大于小于p、q 进行向左、右子树的递归
如果当前节点等于p 或者 q 就返回当前节点。

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null) return null;

        int max = Math.max(p.val, q.val);
        int min = Math.min(p.val, q.val);

        if(root.val > max) return lowestCommonAncestor(root.left, p, q);
        if(root.val < min) return lowestCommonAncestor(root.right, p,q);
        return root;
    }
}