二叉树

二叉树的中序遍历 - LeetCode 94

• 左中右

// 递归
public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    inorder(root, result);
    return result;
}
private void inorder(TreeNode root, List<Integer> result) {
    if (root == null) {
        return;
    }
    inorder(root.left, result);
    result.add(root.val);
    inorder(root.right, result);
}
// 迭代
public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null) {
        return result;
    }
    
    Stack<TreeNode> stack = new Stack<>();
    TreeNode current = root;
    
    while (current != null || !stack.isEmpty()) {
        // 一直往左走，把所有左子节点入栈
        while (current != null) {
            stack.push(current);
            current = current.left;
        }
        
        // 弹出栈顶元素（最左的节点）
        current = stack.pop();
        result.add(current.val);
        
        // 处理右子树
        current = current.right;
    }
    
    return result;
}
// 前序迭代
public List<Integer> preorderIter(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    if (root == null) return res;
    
    Deque<TreeNode> stack = new ArrayDeque<>();
    stack.push(root);
    
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        res.add(node.val);
        if (node.right != null) stack.push(node.right);
        if (node.left != null) stack.push(node.left);
    }
    return res;
}
// 后序迭代
public List<Integer> postorderIterOneStack(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode curr = root;
    TreeNode lastVisited = null;
    
    while (curr != null || !stack.isEmpty()) {
        while (curr != null) {
            stack.push(curr);
            curr = curr.left;
        }
        TreeNode peekNode = stack.peek();
        if (peekNode.right != null && lastVisited != peekNode.right) {
            curr = peekNode.right;
        } else {
            res.add(peekNode.val);
            lastVisited = stack.pop();
        }
    }
    return res;
}

迭代法

遍历方式	栈操作特点	栈中元素顺序	根节点访问顺序
前序	根先入栈，右→左入栈	根→右→左	弹出时即访问
中序	沿左子树入栈	左最深→根	弹出时访问
后序	可用两个栈 / 一个栈记录上次访问	左→右→根	根最后访问

验证BST - LeetCode 98

• 简单解法：中序遍历的结果放到一个新数组，看是不是单调递增，是的话就是BST
• 可以不用数组保存：
  • 用一个变量 prev 记录上一个访问过的节点的值
  • 每访问一个节点时，比较它的值是否比 prev 大（必须严格递增）
  • 如果发现不满足，直接返回 false
  • 如果遍历完所有节点都满足，则返回 true

class Solution {
    private long prev = Long.MIN_VALUE;
    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }
        if (!isValidBST(root.left)) {
            return false;
        }

        if (root.val <= prev) { // 遍历的前一个节点大于等于当前节点，无法满足BST。不能等于因为BST的节点值不能重复
            return false;
        }
        prev = root.val;

        return isValidBST(root.right);
    }
}

恢复BST - LeetCode 99

• BST刚好有两个节点被交换了，恢复BST
• 中序遍历的结果是单调递增的，所以如果发现两个节点不满足单调递增，就是被交换了
• 用两个变量记录这两个节点，然后交换它们的值

class Solution {
    private TreeNode prev = null;
    private TreeNode first = null; 
    private TreeNode second = null;
    public void recoverTree(TreeNode root) {
        recover(root);
        if (first != null && second != null) {
            int temp = first.val;
            first.val = second.val;
            second.val = temp;
        }
    }

    private void recover(TreeNode root){
        if (root == null) return;
        recover(root.left);
        // 当前节点值小于前一个节点值，说明出错了（中序遍历应该是升序）
        if(prev!=null && root.val<prev.val){
            // 第一次发现逆序对，记录前一个较大节点为 first，当前较小为 second
            if(first==null){
                first = prev;
                second = root;
                // 第二次逆序对更新 second（例如：两个错位节点不相邻）
            } else{
                second = root;
            }
        }
        prev = root;
        recover(root.right);
    }
}

判断两颗二叉树是否相同 - LeetCode 100

• 前序遍历 中左右

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) return true;
        if (p == null || q == null) return false; // 一个为空，一个不为空，false
        if (p.val != q.val) return false; // 值不相等，false
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right); // 递归判断左右子树
    }
}

判断两颗二叉树是否对称 - LeetCode 101

• 前序遍历 中左右

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) return true;
        return preOrder(root.left, root.right);
    }
    private boolean preOrder(TreeNode left, TreeNode right){
        if (left == null && right == null) return true;
        if (left == null || right == null) return false;
        if(left.val != right.val) return false;
        return preOrder(left.left,right.right) && preOrder(left.right,right.left);
    }
}

二叉树层序遍历 - LeetCode 102

• 广度优先遍历
• 需要借用一个辅助数据结构即队列来实现，队列先进先出，符合一层一层遍历的逻辑
• 每一层遍历完，需要将队列中的元素出队，并将其左右子节点入队

class Solution {
    public List<List<Integer>> resList = new ArrayList<>();
    public List<List<Integer>> levelOrder(TreeNode root) {
        bfs(root);
        return resList;
    }
    //BFS--迭代方式--借助队列
    public void bfs(TreeNode node) {
        if (node == null) return;
        Queue<TreeNode> que = new LinkedList<TreeNode>(); 
        que.offer(node); // 根节点入队

        while (!que.isEmpty()) {
            List<Integer> itemList = new ArrayList<>(); // 记录每层的节点值
            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--; // 当前层节点数减1
            }
            resList.add(itemList); // 记录当前层节点值
        }
    }
}

二叉树的右视图 - LeetCode 199

• BFS层序遍历，然后找到每层最后（右）一个节点

class Solution {
    public List<Integer> resList = new ArrayList<>(); // 存储每层最后一个节点
    public List<Integer> rightSideView(TreeNode root) {
        bfs(root);
        return resList;
    }
    public void bfs(TreeNode node){
        if (node == null) return; // 如果当前节点为空，返回
        Queue<TreeNode> queue = new LinkedList<>(); // 队列
        queue.offer(node); // 根节点入队
        while (!queue.isEmpty()){
            int len = queue.size(); // 当前这一层的节点总数
            while (len > 0){ // 遍历当前层节点
                TreeNode tmpNode = queue.poll(); // 当前层节点出队
                if (tmpNode.left != null) queue.offer(tmpNode.left); // 下一层左子节点入队
                if (tmpNode.right != null) queue.offer(tmpNode.right); // 下一层右子节点入队
                len--; 
                if (len == 0) resList.add(tmpNode.val); // 说明当前层已经处理完毕，最后一个节点就是我们要的右视图节点，加入结果集
            }
        }
    }
}

二叉树的最近公共祖先 - LeetCode 236

• 自底向上查找就好了，这样就可以找到公共祖先了
• 后序遍历 左右中

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null || root == p || root == q) return root; // 终止条件：遇到 null 或遇到 p/q 本身，直接返回

        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if(left == null && right == null) { // 若未找到节点 p 或 q
            return null;
        }else if(left == null && right != null) { // 若找到一个节点 右子树
            return right;
        }else if(left != null && right == null) { // 若找到一个节点 左子树
            return left;
        }else { // 若找到两个节点
            return root;
        }
    }
}

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

• 利用BST的性质，左子树的值都小于根节点，右子树的值都大于根节点

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) return null;
        if (root.val > p.val && root.val > q.val) { // 如果p和q的值都小于根节点，则它们的公共祖先在左子树
            return lowestCommonAncestor(root.left, p, q);
        } else if (root.val < p.val && root.val < q.val) { // 如果p和q的值都大于根节点，则它们的公共祖先在右子树
            return lowestCommonAncestor(root.right, p, q);
        } else { // 如果p和q的值一个大于根节点，一个小于根节点，则它们的公共祖先就是根节点
            return root;
        }
    }
}

二叉树的最大深度 - LeetCode 104

• 后序遍历 左右中

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

翻转二叉树 - LeetCode 226

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

从前序与中序遍历序列构造二叉树 - LeetCode 105

• 前序遍历的第一个元素 一定是整棵树的根
• 在中序遍历中，根左边的是左子树，右边的是右子树
• 所以前序确定“谁是根”，中序确定“左右子树范围”

class Solution {
    private Map<Integer, Integer> indexMap; // key是节点值，value是节点索引

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int n = preorder.length;
        // 构造哈希映射，帮助我们快速定位根节点
        indexMap = new HashMap<Integer, Integer>(); // key: 节点值，value: 节点索引
        for (int i = 0; i < n; i++) {
            indexMap.put(inorder[i], i); // 存放中序遍历的值和索引
        }
        return myBuildTree(preorder, inorder, 0, n - 1, 0, n - 1); // 参数：前序遍历数组，中序遍历数组，前序遍历左边界，前序遍历右边界，中序遍历左边界，中序遍历右边界
    }

    public TreeNode myBuildTree(int[] preorder, int[] inorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right) {
        if (preorder_left > preorder_right) { // 当前递归范围内没有任何节点了，所以返回 null 
            return null;
        }

        // 前序遍历中的第一个节点就是根节点
        int preorder_root = preorder_left;
        // 在中序遍历中定位根节点
        int inorder_root = indexMap.get(preorder[preorder_root]);
        
        // 先把根节点建立出来
        TreeNode root = new TreeNode(preorder[preorder_root]);
        // 得到左子树中的节点数目 用于划分前序遍历中的左右子树区间
        int size_left_subtree = inorder_root - inorder_left;

        // 递归地构造左子树，并连接到根节点
        // 先序遍历中「从 左边界+1 开始的 size_left_subtree」个元素就对应了中序遍历中「从 左边界 开始到 根节点定位-1」的元素
        root.left = myBuildTree(preorder, inorder, preorder_left + 1, preorder_left + size_left_subtree, inorder_left, inorder_root - 1);

        // 递归地构造右子树，并连接到根节点
        // 先序遍历中「从 左边界+1+左子树节点数目 开始到 右边界」的元素就对应了中序遍历中「从 根节点定位+1 到 右边界」的元素
        root.right = myBuildTree(preorder, inorder, preorder_left + size_left_subtree + 1, preorder_right, inorder_root + 1, inorder_right);

        return root;
    }
}

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

• 后序遍历的最后一个元素 一定是整棵树的根
• 在中序遍历中，根左边的是左子树，右边的是右子树
• 所以后序确定“谁是根”，中序确定“左右子树范围”

class Solution {
    private Map<Integer, Integer> indexMap; // 用于快速查找中序中节点位置

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        int n = inorder.length;
        indexMap = new HashMap<>();
        for (int i = 0; i < n; i++) {
            indexMap.put(inorder[i], i);
        }
        return build(inorder, postorder, 0, n - 1, 0, n - 1);
    }

    private TreeNode build(int[] inorder, int[] postorder,
                           int in_left, int in_right,
                           int post_left, int post_right) {
        if (in_left > in_right) { // 当前递归范围内没有任何节点了，所以返回 null
            return null;
        }

        // 后序遍历的最后一个节点是根节点
        int rootVal = postorder[post_right];
        TreeNode root = new TreeNode(rootVal);

        // 在中序遍历中定位根节点
        int index = indexMap.get(rootVal);

        // 左子树节点数
        int leftSize = index - in_left;

        // 构建左子树
        root.left = build(inorder, postorder,
                          in_left, index - 1,
                          post_left, post_left + leftSize - 1);

        // 构建右子树
        root.right = build(inorder, postorder,
                           index + 1, in_right,
                           post_left + leftSize, post_right - 1);

        return root;
    }
}

填充每个节点的下一个右侧节点指针II - LeetCode 117

• 第一种方法：队列层序遍历
• 第二种方法：用next指针遍历每一层 O(1)空间
  • curr：指向当前正在处理的一层的节点（从 root 开始）
  • dummy：一个假头节点，用于构造下一层的链表
  • dummy.next：每次处理完当前层后，这里就是“下一层的起始节点”
  • 外层 while (curr != null)：一层一层处理
  • 内层 while (curr != null)：处理当前层所有节点

public Node connect(Node root) {
    Node dummy = new Node(0); // 虚拟头节点，用于连接下一层
    Node curr = root;         // 当前遍历层
    while (curr != null) {
        Node pre = dummy;     // “缝针”的指针，一开始从 dummy 开始
        dummy.next = null;    // 清空上一层构造的“下一层起始点
        
        while (curr != null) { // 遍历当前层节点
            if (curr.left != null) { // 连接左子节点
                pre.next = curr.left;
                pre = pre.next; // 移动到下一个节点
            }
            if (curr.right != null) { // 连接右子节点
                pre.next = curr.right;
                pre = pre.next; // 移动到下一个节点
            }
            curr = curr.next; // 同层右移
        }
        curr = dummy.next;    // 换到下一层
    }
    return root;
}

二叉树展开为链表 - LeetCode 114

public void flatten(TreeNode root) {
    TreeNode curr = root; // 当前节点
    while (curr != null) { // 遍历当前节点  
        if (curr.left != null) {
            TreeNode next = curr.left;
            TreeNode predecessor = next;
            while (predecessor.right != null) {
                predecessor = predecessor.right; // 找到左子树的最右节点
            }
            predecessor.right = curr.right; // 将右子树接到左子树的最右节点
            curr.left = null; // 断开左子树
            curr.right = next; // 将左子树接到当前节点
        }
        curr = curr.right;
    }
}

路经总和 - LeetCode 112

public boolean hasPathSum(TreeNode root, int targetSum) {
    if (root == null) return false; // 如果当前节点为空，返回 false
    if (root.left == null && root.right == null) return root.val == targetSum; // 如果当前节点是叶子节点，判断路径和是否等于 targetSum
    return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val); // 递归判断左右子树
}

路径总和II - LeetCode 113

class Solution {
    // 存储所有符合条件的路径
    List<List<Integer>> ret = new LinkedList<>();
    // 存储当前递归路径上的节点值
    Deque<Integer> path = new LinkedList<>();

    /**
     * 主函数，返回所有路径和为 targetSum 的路径
     * @param root 二叉树根节点
     * @param targetSum 目标路径和
     * @return 所有符合条件的路径列表
     */
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        dfs(root, targetSum); // 从根节点开始深度优先遍历
        return ret;
    }

    /**
     * 深度优先搜索（DFS）+ 回溯
     * @param root 当前节点
     * @param targetSum 剩余需要匹配的路径和
     */
    public void dfs(TreeNode root, int targetSum) {
        if (root == null) { // 遍历到空节点直接返回
            return;
        }

        // 1. 处理当前节点
        path.offerLast(root.val); // 将当前节点值加入路径
        targetSum -= root.val;    // 目标和减去当前节点值

        // 2. 判断是否满足条件
        if (root.left == null && root.right == null && targetSum == 0) {
            // 当前节点是叶子节点，且路径和正好等于目标值
            ret.add(new LinkedList<>(path)); // 将当前路径的拷贝加入结果集
        }

        // 3. 递归处理左右子树
        dfs(root.left, targetSum);
        dfs(root.right, targetSum);

        // 4. 回溯（撤销当前节点的选择）
        path.pollLast(); // 删除当前节点，回到上一个节点
    }
}

求根节点到叶子节点数字之和 - LeetCode 129

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

public int dfs(TreeNode root, int prevSum) {
    if (root == null) return 0;  // 空节点不贡献数字，返回0
    int sum = prevSum * 10 + root.val;  // 计算当前路径数字（拼接数字）
    if (root.left == null && root.right == null) {  // 到叶子节点
        return sum;  // 返回这一条路径代表的数字
    } else {
        // 递归左子树和右子树路径和累加
        return dfs(root.left, sum) + dfs(root.right, sum);
    }
}

二叉树的最大路径和 - LeetCode 124

class Solution {
    int maxSum = Integer.MIN_VALUE; // 全局最大路径和

    public int maxPathSum(TreeNode root) {
        maxGain(root);
        return maxSum;
    }

    public int maxGain(TreeNode node) {
        if (node == null) return 0;
    
        // 递归计算左右子节点的最大贡献值
        // 只有在最大贡献值大于 0 时，才会选取对应子节点
        int leftGain = Math.max(maxGain(node.left), 0);
        int rightGain = Math.max(maxGain(node.right), 0);

        // 当前节点作为“拐点”时的路径和（用于尝试更新最大值）
        int priceNewpath = node.val + leftGain + rightGain;

        // 更新答案
        maxSum = Math.max(maxSum, priceNewpath);

        // 返回节点的最大贡献值
        // 递归 = 多层函数互相调用，每一层 return 给上层，上层继续。不是 return 一次就全部结束了。
        return node.val + Math.max(leftGain, rightGain); // 从 node 往上传递路径时，不能走左右两边，只能选一边走上去，所以取较大一边
    }
}

二叉搜索树迭代器 - LeetCode 173

class BSTIterator {
    private int idx;              // 当前遍历到第几个元素
    private List<Integer> arr;   // 存储中序遍历的结果（升序）

    public BSTIterator(TreeNode root) {
        idx = 0;
        arr = new ArrayList<Integer>();
        inorderTraversal(root, arr); // 把 BST 中序遍历结果放入 arr 中
    }

    public int next() {
        return arr.get(idx++); // 返回当前元素，并移动到下一个元素
    }

    public boolean hasNext() {
        return idx < arr.size(); // 判断是否还有下一个元素
    }

    private void inorderTraversal(TreeNode root, List<Integer> arr) {
        if (root == null) return;
        inorderTraversal(root.left, arr);
        arr.add(root.val); // 中序遍历，先遍历左子树，再遍历根节点，再遍历右子树
        inorderTraversal(root.right, arr);
    }
}

完全二叉树的节点个数 - LeetCode 222

• 完全二叉树只有两种情况，情况一：就是满二叉树，情况二：最后一层叶子节点没有满。

// 普通二叉树 递归方法
public int countNodes(TreeNode root) {
    if(root == null) {
        return 0;
    }
    return countNodes(root.left) + countNodes(root.right) + 1;
}

/**
 * 针对完全二叉树的解法
 * 完全二叉树的特点：
 * 除了最后一层外，其他层都是满的；
 * 最后一层的节点都在左侧连续排列。
 * 因此，可以通过判断子树的深度，直接计算子树节点个数，而不是一层层数。
 * 满二叉树的结点数为：2^depth - 1
 */
public int countNodes(TreeNode root) {
    if (root == null) return 0;
    TreeNode left = root.left;
    TreeNode right = root.right;
    int leftDepth = 0, rightDepth = 0; // 这里初始为0是有目的的，为了下面求指数方便
    while (left != null) {  // 求左子树深度
        left = left.left;
        leftDepth++;
    }
    while (right != null) { // 求右子树深度
        right = right.right;
        rightDepth++;
    }
    if (leftDepth == rightDepth) {
        return (2 << leftDepth) - 1; // 注意(2<<1) 相当于2^2，所以leftDepth初始为0
    }
    return countNodes(root.left) + countNodes(root.right) + 1; // 如果不是满二叉树，则递归计算左右子树 +1是因为要加上当前节点
}

二叉树的最近公共祖先 - LeetCode 236

public TreeNode lowestCommonAncestor(TreeNode node, TreeNode p, TreeNode q) {
    if(node == null || node ==p || node==q) return node; // 找到 p 或 q，或者到达叶子节点，返回 
    TreeNode left = lowestCommonAncestor(node.left,p,q); // 递归左子树
    TreeNode right = lowestCommonAncestor(node.right,p,q); // 递归右子树

    if(left != null && right != null){ // 如果左右子树都找到 p 或 q，则当前节点就是最近公共祖先
        return node;
    }

    return left != null ? left: right; // 如果左子树找到 p 或 q，则返回左子树，否则返回右子树
}

二叉树的层平均值 - LeetCode 637

public List<Double> averageOfLevels(TreeNode root) {
    List<Double> averages = new ArrayList<Double>(); // 存储每层平均值
    Queue<TreeNode> queue = new LinkedList<TreeNode>(); // 队列
    queue.offer(root); // 根节点入队
    while (!queue.isEmpty()) { // 队列不为空
        double sum = 0; // 当前层节点值之和
        int size = queue.size(); // 当前层节点数
        for (int i = 0; i < size; i++) { // 遍历当前层节点
            TreeNode node = queue.poll(); // 当前层节点出队
            sum += node.val; // 当前层节点值之和
            TreeNode left = node.left, right = node.right; // 当前层节点左右子节点
            if (left != null) { // 左子节点不为空，入队
                queue.offer(left);
            }
            if (right != null) { // 右子节点不为空，入队
                queue.offer(right);
            }
        } // 当前层节点处理完毕
        averages.add(sum / size); // 计算当前层平均值，加入结果集
    }
    return averages;
}

二叉树的锯齿形层序遍历 - LeetCode 103

• 锯齿形层序遍历 。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
• 本质是层序遍历，只不过需要交替从左到右和从右到左。

public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    List<List<Integer>> ans = new LinkedList<>(); // 存储结果
    if (root == null) return ans; // 如果根节点为空，返回空结果
    Queue<TreeNode> nodeQueue = new ArrayDeque<>(); // 队列
    nodeQueue.offer(root); // 根节点入队
    boolean isOrderLeft = true; // 是否从左到右 true 从左到右，false 从右到左
    while (!nodeQueue.isEmpty()) {
        Deque<Integer> levelList = new LinkedList<>(); // 存储当前层节点值
        int size = nodeQueue.size(); // 当前层节点数
        for (int i = 0; i < size; ++i) { // 遍历当前层节点
            TreeNode curNode = nodeQueue.poll(); // 当前层节点出队
            if (isOrderLeft) { // 从左到右
                levelList.offerLast(curNode.val); // 加入队尾
            } else { // 从右到左
                levelList.offerFirst(curNode.val); // 加入队首
            }
            if (curNode.left != null) { // 左子节点不为空，入队
                nodeQueue.offer(curNode.left);
            }
            if (curNode.right != null) { // 右子节点不为空，入队
                nodeQueue.offer(curNode.right);
            }
        }
        ans.add(new LinkedList<Integer>(levelList)); // 将当前层节点值加入结果集
        isOrderLeft = !isOrderLeft; // 切换方向
    }
    return ans;
}

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

• 中序遍历 因为二叉搜索树中序遍历是升序的 所以相邻节点差值最小

class Solution {
    int pre; // 前一个节点
    int ans; // 最小绝对差

    public int getMinimumDifference(TreeNode root) {
        ans = Integer.MAX_VALUE;
        pre = -1;
        dfs(root);
        return ans;
    }

    public void dfs(TreeNode root) {
        if (root == null) return; // 如果当前节点为空，返回
        dfs(root.left); // 递归左子树
        if (pre == -1) { // 如果前一个节点为空，则当前节点为前一个节点
            pre = root.val;
        } else {
            ans = Math.min(ans, root.val - pre); // 更新最小绝对差
            pre = root.val; // 更新前一个节点
        }
        dfs(root.right); // 递归右子树
    }
}

二叉搜索树第K小的元素 - LeetCode 230

• 因为中序遍历是升序的，所以第 k 个访问的节点就是答案。

class Solution {
    int count = 0;     // 当前访问的节点数量
    int result = 0;    // 第 k 小节点的值

    public int kthSmallest(TreeNode root, int k) {
        inorder(root, k);
        return result;
    }

    private void inorder(TreeNode node, int k) {
        if (node == null) return;

        inorder(node.left, k);

        count++;
        if (count == k) {
            result = node.val;
            return;  // 提前结束遍历
        }

        inorder(node.right, k);
    }
}

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

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return helper(nums, 0, nums.length - 1); // 参数：
        // 1. 数组 nums
        // 2. 左边界 left
        // 3. 右边界 right
    }

    public TreeNode helper(int[] nums, int left, int right) { // 下标 left 和 right 是数组 nums 的左右边界
        if (left > right) { // 终止条件：如果左边界大于右边界，则返回 null  
            return null;
        }

        // 总是选择中间位置左边的数字作为根节点
        int mid = (left + right) / 2; // 中间位置

        TreeNode root = new TreeNode(nums[mid]); // 创建根节点
        root.left = helper(nums, left, mid - 1); // 递归左子树
        root.right = helper(nums, mid + 1, right); // 递归右子树
        return root;
    }
}

建立四叉树 - LeetCode 427

class Solution {
    public Node construct(int[][] grid) {
        // (0, 0, n, n) 表示从左上角开始，到整个 grid 的右下角（即一个 n x n 正方形区域）。
        return dfs(grid, 0, 0, grid.length, grid.length); 
    
    }

    public Node dfs(int[][] grid, int r0, int c0, int r1, int c1) { // 参数：r0左上角的row，c0左上角的col，r1右下角的row，c1右下角的col
        
        boolean same = true; // 是否所有元素都相同
        for (int i = r0; i < r1; ++i) {
            for (int j = c0; j < c1; ++j) {
                if (grid[i][j] != grid[r0][c0]) { // 拿当前元素和左上角元素比较 因为左上角元素是当前正方形的第一个元素，如果当前元素和左上角元素不同，则不是所有元素都相同
                    same = false; // 如果发现有不同元素，则不是所有元素都相同
                    break;
                }
            }
            if (!same) {
                break; // break 在 Java 中 只跳出当前最近的循环层，不会直接跳出双重循环。所以这里需要break两次
            }
        }

        if (same) {
            return new Node(grid[r0][c0] == 1, true); // 如果所有元素都相同，则返回一个节点
        }

        int midR = (r0+r1)/2; // 中间行
        int midC = (c0+c1)/2; // 中间列
        Node res = new Node(true,false,
            dfs(grid, r0, c0, midR, midC),      // 左上角
            dfs(grid, r0, midC, midR, c1),      // 右上角
            dfs(grid, midR, c0, r1, midC),      // 左下角
            dfs(grid, midR, midC, r1, c1)       // 右下角
        );
        return res; // 返回节点
    }
}

二叉树的直径 - LeetCode 543

class Solution {
    int ans = 0; // 记录最大直径（按边数计）
    public int diameterOfBinaryTree(TreeNode root) {
        depth(root);
        return ans;
    }

    public int depth(TreeNode root) {
        if (root == null) { 
            // 空节点深度定义为 -1，这样叶子节点返回深度 0
            return -1;
        }
        int depth1 = depth(root.left) + 1;  // 左子树深度（边数）
        int depth2 = depth(root.right) + 1; // 右子树深度（边数）
        // 更新直径：经过当前节点的最长路径 = 左深度 + 右深度
        ans = Math.max(ans, depth1 + depth2);
        // 返回当前节点为根的子树的最大深度
        return Math.max(depth1, depth2);
    }
}

二叉树最大宽度 - LeetCode 662

• 完全二叉树编号法（根节点编号 1，左子 = index*2，右子 = index*2+1）
• 宽度 = 同一层最右节点的编号 − 最左节点的编号 + 1

class Solution {
    Map<Integer, Integer> levelMin = new HashMap<>(); // 记录每层最左边的节点索引 key: 层数，value: 最左边的节点索引

    public int widthOfBinaryTree(TreeNode root) {
        return dfs(root, 1, 1);
    }

    public int dfs(TreeNode node, int depth, int index) { // node: 当前节点，depth: 当前层数，index: 当前节点索引
        if (node == null) {
            return 0;
        }
        levelMin.putIfAbsent(depth, index); // 每一层最先访问到的节点会是最左边的节点，即每一层编号的最小值
        return Math.max(
            index - levelMin.get(depth) + 1, // 当前层宽度
            Math.max(
                dfs(node.left, depth+1, index*2), // 递归左子树
                dfs(node.right, depth+1, index*2+1) // 递归右子树
            )
        );
    }
}