算法 3（二叉树、图论、回溯算法）

/* 二叉树节点类 */
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;
    }
}

// 初始化节点
TreeNode n1 = new TreeNode(1);
TreeNode n2 = new TreeNode(2);
TreeNode n3 = new TreeNode(3);
TreeNode n4 = new TreeNode(4);
TreeNode n5 = new TreeNode(5);
// 构建节点之间的引用（指针）
n1.left = n2;
n1.right = n3;
n2.left = n4;
n2.right = n5;

TreeNode P = new TreeNode(0);
// 在 n1 -> n2 中间插入节点 P
n1.left = P;
P.left = n2;
// 删除节点 P
n1.left = n2;

/* 前序遍历 */
public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    preorder(root,res);
    return res;
}
// 使用一个辅助方法，传递同一个列表对象，避免每次递归 new ArrayList 和 addAll 的性能开销
public void preorder(TreeNode root,List<Integer> res){
    if(root == null) return;
    res.add(root.val);
    preorder(root.left, res);
    preorder(root.right, res);
}

/* 中序遍历 */
public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    inorder(root, res);
    return res;
}
public void inorder(TreeNode root, List<Integer> res) {
    if (root == null)
        return;
    inorder(root.left, res);
    res.add(root.val);
    inorder(root.right, res);
}

/* 后序遍历 */
public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    postorder(root, res);
    return res;
}
public void postorder(TreeNode root, List<Integer> res){
    if(root == null) return;
    postorder(root.left, res);
    postorder(root.right, res);
    res.add(root.val);
}

/* 层序遍历 */
List<Integer> levelOrder(TreeNode root) {
    // 初始化队列，加入根节点
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    // 初始化一个列表，用于保存遍历序列
    List<Integer> list = new ArrayList<>();
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll(); // 队列出队
        list.add(node.val);           // 保存节点值
        if (node.left != null)
            queue.offer(node.left);   // 左子节点入队
        if (node.right != null)
            queue.offer(node.right);  // 右子节点入队
    }
    return list;
}

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        order(root, res);
        return res;
    }

    public void order(TreeNode root, List<List<Integer>> res) {
        if (root == null) return;
        Queue<TreeNode> que = new LinkedList<TreeNode>();
        que.offer(root);

        while (!que.isEmpty()) {
            // 【关键】获取当前层的节点数，实现分层
            int size = que.size();
            List<Integer> currentLevel = new ArrayList<>();

            for (int i = 0; i < size; i++) {
                TreeNode node = que.poll();
                // 将值添加到“当前层”的列表，而不是直接添加到 res
                currentLevel.add(node.val);

                if (node.left != null) que.offer(node.left);
                if (node.right != null) que.offer(node.right);
            }
            // 将“当前层”的列表添加到总结果 res 中
            res.add(currentLevel);
        }
    }
}

// 前序遍历（迭代）顺序：中-左-右，入栈顺序：中-右-左
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;
    }
}

// 中序遍历（迭代）顺序: 左-中-右，入栈顺序：左-右
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;
    }
}

// 后序遍历（迭代）顺序：左-右-中，入栈顺序：中-左-右，出栈顺序：中-右-左，最后翻转结果
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;
    }
}

TreeNode* invertTree(TreeNode* root)

if (root == NULL) return root;

// 递归实现前序遍历
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        swap(root);
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }
    private void swap(TreeNode root) {
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
    }
}

// 后序遍历也行
invertTree(root.left);
invertTree(root.right);
swap(root);

bool compare(TreeNode* left, TreeNode* right)

if (left == NULL && right != NULL) return false;
else if (left != NULL && right == NULL) return false;
else if (left == NULL && right == NULL) return true;
else if (left->val != right->val) return false; // 注意这里我没有使用else

// 后序遍历（递归）的变形
public boolean isSymmetric(TreeNode root) {
    return compare(root.left, root.right);
}

private boolean compare(TreeNode left, TreeNode right) {
    if (left == null && right != null) {
        return false;
    }
    if (left != null && right == null) {
        return false;
    }
    if (left == null && right == null) {
        return true;
    }
    if (left.val != right.val) {
        return false;
    }

    // 可以看出使用的遍历方式，左子树左右中，右子树右左中
    // 1、比较外侧
    // 左子树：左、 右子树：右
    boolean compareOutside = compare(left.left, right.right);

    // 2、比较内侧
    // 左子树：右、 右子树：左
    boolean compareInside = compare(left.right, right.left);

    // 3、逻辑处理
    // 左子树：中、 右子树：中
    return compareOutside && compareInside;
}

// 求深度用前序遍历（递归）
class Solution {
    // 定义一个成员变量或全局变量来记录最大深度
    private int maxD = 0;

    public int maxDepth(TreeNode root) {
        // 重置最大深度，防止多次调用受影响
        maxD = 0;
        // 【中】：从根节点开始，当前深度为 1
        // 调用辅助函数，传入当前节点和当前深度
        preorder(root, 1);
        return maxD;
    }

    // 辅助函数：前序遍历 (中 -> 左 -> 右)
    // node: 当前节点
    // depth: 当前节点的深度 (从父节点传下来的)
    private void preorder(TreeNode node, int depth) {
        if (node == null) {
            return;
        }
        // 【中】：处理当前节点
        // 在进入子节点之前，先利用当前深度更新全局最大深度
        maxD = depth > maxD ? depth : maxD;
        // 【左】：遍历左子树，深度 + 1
        preorder(node.left, depth + 1);
        // 【右】：遍历右子树，深度 + 1
        preorder(node.right, depth + 1);
    }
}

// 后序遍历（递归）
class Solution {
    public int maxDepth(TreeNode root) {
        if(root == null) return 0; // 空节点 (null) 代表没有层数，所以返回 0
        int left = maxDepth(root.left);
        int right = maxDepth(root.right);
        return left>right ? left+1 :right+1;
    }
}

int getDepth(TreeNode* node)

if (node == NULL) return 0;

// 后序遍历（递归），比求最大深度复杂一些
class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftDepth = minDepth(root.left);
        int rightDepth = minDepth(root.right);
        if (root.left == null) {
            return rightDepth + 1;
        }
        if (root.right == null) {
            return leftDepth + 1;
        }
        // 左右结点都不为null
        return Math.min(leftDepth, rightDepth) + 1;
    }
}

// 通用后序递归遍历解法
public int countNodes(TreeNode root) {
    if(root == null) {
        return 0;
    }
    int leftNum = countNodes(root.left);      // 左
    int rightNum = countNodes(root.right);    // 右
    return leftNum + rightNum + 1;      // 中
}

// 层序遍历迭代法
public int countNodes(TreeNode root) {
    if(root == null) return 0;
    // 初始化队列，加入根节点
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    int sum = 0;
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll(); // 队列出队
        sum++;
        if (node.left != null)
            queue.offer(node.left);   // 左子节点入队
        if (node.right != null)
            queue.offer(node.right);  // 右子节点入队
    }
    return sum;
}

// -1 表示已经不是平衡二叉树了，否则返回值是以该节点为根节点树的高度
int getHeight(TreeNode* node)

if (node == NULL) {
    return 0;
}

// 后序遍历（递归）
class Solution {
    public boolean isBalanced(TreeNode root) {
        return dfs(root) != -1;
    }

    public int dfs(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftHeight = dfs(root.left);
        // 【⚠️容易遗漏】必须在获取到子树返回值后，立刻检查是否为 -1。如果是，直接向上抛出 -1，不再参与后续的左右子树高度比较
        if (leftHeight == -1) {
            return -1;
        }
        int rightHeight = dfs(root.right);
        if (rightHeight == -1) {
            return -1;
        }
        // 左右子树高度差大于1，return -1表示已经不是平衡树了
        if (Math.abs(leftHeight - rightHeight) > 1) {
            return -1;
        }
        return Math.max(leftHeight, rightHeight) + 1;
    }
}

if (node.left != NULL && node.left.left == NULL && node.left.right == NULL) {
    // 左叶子节点处理逻辑
}

if (root == NULL) return 0;
if (root->left == NULL && root->right== NULL) return 0; //其实这个也可以不写，不影响结果，只会让递归多进行一层

// 前序遍历（递归）
public int sumOfLeftLeaves(TreeNode root) {
    if (root == null) return 0;
    int midValue = 0;
    if (root.left != null && root.left.left == null && root.left.right == null) {
        midValue = root.left.val;
    }
    int sum = midValue + sumOfLeftLeaves(root.left) + sumOfLeftLeaves(root.right);  // 中左右
    return sum;
}

// 层序遍历（迭代）
public int findBottomLeftValue(TreeNode root) {
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    int res = 0;
    while (!queue.isEmpty()) {
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            TreeNode poll = queue.poll();
            if (i == 0) {
                res = poll.val;
            }
            if (poll.left != null) {
                queue.offer(poll.left);
            }
            if (poll.right != null) {
                queue.offer(poll.right);
            }
        }
    }
    return res;
}

class Solution {
    private int Deep = -1;
    private int value = 0;
    public int findBottomLeftValue(TreeNode root) {
        value = root.val;
        findValue(root,0);
        return value;
    }

    private void findValue (TreeNode root,int deep) {
        if (root == null) return;
        if (root.left == null && root.right == null) {
            if (deep > Deep) {
                value = root.val;
                Deep = deep;
            }
        }
        if (root.left != null) findValue(root.left, deep + 1); // 这里的deep+1用到了回溯
        if (root.right != null) findValue(root.right, deep + 1); // 同理
    }
}

public boolean hasPathSum(TreeNode root, int targetSum)

if(cur == null) return false;
if (!cur.left && !cur.right && count == 0) return true; // 遇到叶子节点，并且计数为0
if (!cur.left && !cur.right) return false; // 遇到叶子节点而没有找到合适的边，直接返回

// 左
// 遇到叶子节点返回true，则直接返回true
if (traversal(cur.left, count - cur.left.val)) return true; // 回溯

// 右
// 遇到叶子节点返回true，则直接返回true
if (traversal(cur.right, count - cur.right.val)) return true; // 回溯

return false;

// 左
count -= cur.left.val; // 递归，处理节点;
if (traversal(cur.left, count)) return true;
count += cur.left.val; // 回溯，撤销处理结果

// 右
count -= cur.right.val;
if (traversal(cur.right, count)) return true;
count += cur.right.val;

return false;

// 前序遍历（递归）
public boolean hasPathSum(TreeNode root, int targetSum) {
    if (root == null) return false; // 为空退出
    // 叶子节点判断是否符合
    if (root.left == null && root.right == null) return root.val == targetSum;
    // 求两侧分支的路径和
    return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val);
}

// 前序遍历（递归）
class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        dfs(root, 0, res);
        return res;
    }

    private void dfs(TreeNode root, int depth, List<Integer> res) {
        if (root == null) return;
        if (depth == res.size()) // 这个深度首次遇到
            res.add(root.val);
        dfs(root.right, depth + 1, res); // 先递归右子树，保证首次遇到的一定是最右边的节点
        dfs(root.left, depth + 1, res);
    }
}

// 迭代实现BFS
class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        // 1. 初始化队列，将根节点入队
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            // 2. 获取当前层的节点数量
            int size = queue.size();
            // 3. 遍历当前层的所有节点
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll(); // 出队
                // 4. 如果是当前层的最后一个节点，加入结果集
                if (i == size - 1) {
                    res.add(node.val);
                }
                // 5. 将下一层的子节点入队 (先左后右，保证顺序)
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
        }
        return res;
    }
}

// 后序遍历（递归）
class Solution {
    int length = 0; // 路径长度
    public int diameterOfBinaryTree(TreeNode root) {
        if(root==null) return -1;
        depth(root);
        return length;
    }
    public int depth(TreeNode node) {
        if (node == null) {
            return 0; // 访问到空节点了，返回0
        }
        int L = depth(node.left); // 左儿子为根的子树的深度
        int R = depth(node.right); // 右儿子为根的子树的深度
        length = Math.max(length, L+R); // 计算该根节点的最大路径长度即L+R+1，更新length
        return Math.max(L, R) + 1; // 返回该节点为根的子树的深度
    }
}

class Solution {
    public void flatten(TreeNode root) {
        List<TreeNode> list = new ArrayList<>();
        preorderTraversal(root, list);
        int size = list.size();
        for (int i = 1; i < size; i++) {
            TreeNode prev = list.get(i - 1), curr = list.get(i);
            prev.left = null;
            prev.right = curr;
        }
    }

    public void preorderTraversal(TreeNode root, List<TreeNode> list) {
        if (root != null) {
            list.add(root);
            preorderTraversal(root.left, list);
            preorderTraversal(root.right, list);
        }
    }
}

import java.util.Arrays;
class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        // 1. 如果数组为空或非法，返回 null
        if (inorder.length == 0 || postorder.length ==0 || inorder.length != postorder.length) {
            return null;
        }

        // 2. 后序遍历数组最后一个元素，就是当前的中间节点（根节点）
        int rootValue = postorder[postorder.length - 1];
        TreeNode root = new TreeNode(rootValue);

        // 3. 叶子节点情况：如果只有一个元素，直接返回
        if (postorder.length == 1) {
            return root;
        }

        // 4. 找到中序遍历的切割点
        int delimiterIndex = 0;
        for (; delimiterIndex < inorder.length; delimiterIndex++) {
            if (inorder[delimiterIndex] == rootValue) {
                break;
            }
        }

        // 5. 切割中序数组
        // 左闭右开：[0, delimiterIndex)
        int[] leftInorder = Arrays.copyOfRange(inorder, 0, delimiterIndex);
        // [delimiterIndex + 1, end)
        int[] rightInorder = Arrays.copyOfRange(inorder, delimiterIndex + 1, inorder.length);

        // 6. 切割后序数组
        // 左子树的后序遍历：长度与左中序数组相同
        // 范围：[0, leftInorder.length)
        int[] leftPostorder = Arrays.copyOfRange(postorder, 0, leftInorder.length);

        // 右子树的后序遍历
        // 范围：[leftInorder.length, postorder.length - 1)
        // 注意：postorder.length - 1 是因为最后一个元素是根，已经被取出了
        int[] rightPostorder = Arrays.copyOfRange(postorder, leftInorder.length, postorder.length - 1);

        // 7. 递归构建左右子树
        root.left = buildTree(leftInorder, leftPostorder);
        root.right = buildTree(rightInorder, rightPostorder);

        return root;
    }
}

import java.util.HashMap;
import java.util.Map;
class Solution {
    // 用于存储中序遍历中 "值 -> 索引" 的映射，以便 O(1) 时间找到根节点位置
    private Map<Integer, Integer> inorderMap;
    // 后序遍历数组，作为成员变量避免每次递归传递
    private int[] postorderArr;

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if (inorder.length == 0 || postorder.length == 0 || inorder.length != postorder.length) {
            return null;
        }

        // 1. 构建哈希表
        inorderMap = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            inorderMap.put(inorder[i], i);
        }

        this.postorderArr = postorder;

        // 2. 调用递归函数
        // 初始范围：[0, length)，即左闭右开
        return buildHelper(0, inorder.length, 0, postorder.length);
    }

    /**
     * 递归构建树 (左闭右开区间)
     * @param inLeft  中序遍历左边界 (包含)
     * @param inRight 中序遍历右边界 (不包含) -> 有效范围 [inLeft, inRight)
     * @param postLeft 后序遍历左边界 (包含)
     * @param postRight 后序遍历右边界 (不包含) -> 有效范围 [postLeft, postRight)
     */
    private TreeNode buildHelper(int inLeft, int inRight, int postLeft, int postRight) {
        // 终止条件：区间为空 (左边界 >= 右边界)
        if (inLeft >= inRight || postLeft >= postRight) {
            return null;
        }

        // 1. 确定根节点的值
        // 在左闭右开区间 [postLeft, postRight) 中，最后一个元素是 postRight - 1
        int rootVal = postorderArr[postRight - 1];
        TreeNode root = new TreeNode(rootVal);

        // 2. 找到根节点在中序遍历中的索引
        int inRootIndex = inorderMap.get(rootVal);

        // 3. 计算左子树的节点数量
        // 中序遍历中，左子树范围是 [inLeft, inRootIndex)
        int leftSize = inRootIndex - inLeft;

        // 4. 递归构建左子树
        // 中序：[inLeft, inRootIndex)
        // 后序：[postLeft, postLeft + leftSize)
        // 解释：后序的左子树从 postLeft 开始，长度为 leftSize
        root.left = buildHelper(
            inLeft,
            inRootIndex,
            postLeft,
            postLeft + leftSize
        );

        // 5. 递归构建右子树
        // 中序：[inRootIndex + 1, inRight)
        // 后序：[postLeft + leftSize, postRight - 1)
        // 解释：
        //   - 后序左边界：跳过左子树部分 (postLeft + leftSize)
        //   - 后序右边界：当前区间的右边界 (postRight) 需要减去 1，因为最后一位是根节点
        root.right = buildHelper(
            inRootIndex + 1,
            inRight,
            postLeft + leftSize,
            postRight - 1
        );

        return root;
    }
}

import java.util.Arrays;
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        // 1. 前序遍历数组第一个元素，就是当前的根节点
        int rootValue = preorder[0];
        TreeNode root = new TreeNode(rootValue);

        // 2. 叶子节点情况
        if (preorder.length == 1) {
            return root;
        }

        // 3. 找到中序遍历的切割点 (根节点位置)
        int delimiterIndex = 0;
        for (; delimiterIndex < inorder.length; delimiterIndex++) {
            if (inorder[delimiterIndex] == rootValue) {
                break;
            }
        }

        // 4. 切割中序数组
        // 左子树中序: [0, delimiterIndex)
        int[] leftInorder = Arrays.copyOfRange(inorder, 0, delimiterIndex);
        // 右子树中序: [delimiterIndex + 1, end)
        int[] rightInorder = Arrays.copyOfRange(inorder, delimiterIndex + 1, inorder.length);

        // 5. 切割前序数组
        // 左子树大小
        int leftSize = leftInorder.length;

        // 左子树前序: [1, 1 + leftSize)
        // 注意：前序的第0个是根，所以左子树从索引1开始
        int[] leftPreorder = Arrays.copyOfRange(preorder, 1, 1 + leftSize);

        // 右子树前序: [1 + leftSize, end)
        int[] rightPreorder = Arrays.copyOfRange(preorder, 1 + leftSize, preorder.length);

        // 6. 递归构建
        root.left = buildTree(leftPreorder, leftInorder);
        root.right = buildTree(rightPreorder, rightInorder);

        return root;
    }
}

import java.util.HashMap;
import java.util.Map;
class Solution {
    // 存储中序遍历的值到索引的映射
    private Map<Integer, Integer> inorderMap;
    // 保存前序遍历数组引用
    private int[] preorderArr;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder == null || inorder == null || preorder.length != inorder.length) {
            return null;
        }

        // 1. 预处理：构建中序遍历哈希表
        inorderMap = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            inorderMap.put(inorder[i], i);
        }

        this.preorderArr = preorder;

        // 2. 调用递归函数
        // 初始范围：前序 [0, n), 中序 [0, n)
        return buildHelper(0, preorder.length, 0, inorder.length);
    }

    /**
     * 递归构建 (左闭右开区间)
     * @param preLeft  前序遍历左边界 (包含)
     * @param preRight 前序遍历右边界 (不包含)
     * @param inLeft   中序遍历左边界 (包含)
     * @param inRight  中序遍历右边界 (不包含)
     */
    private TreeNode buildHelper(int preLeft, int preRight, int inLeft, int inRight) {
        // 终止条件：区间为空
        if (preLeft >= preRight || inLeft >= inRight) {
            return null;
        }

        // 1. 确定根节点
        // 前序遍历的第一个元素即为根 (在左闭右开区间中是 preLeft)
        int rootVal = preorderArr[preLeft];
        TreeNode root = new TreeNode(rootVal);

        // 2. 找到根在中序遍历中的位置
        Integer inRootIndex = inorderMap.get(rootVal);

        // 3. 计算左子树的大小
        // 中序左子树范围: [inLeft, inRootIndex)
        int leftSize = inRootIndex - inLeft;

        // 4. 递归构建左子树
        // 前序左子树: [preLeft + 1, preLeft + 1 + leftSize)
        // 解释：跳过根节点(preLeft)，长度为 leftSize
        // 中序左子树: [inLeft, inRootIndex)
        root.left = buildHelper(
            preLeft + 1,
            preLeft + 1 + leftSize,
            inLeft,
            inRootIndex
        );

        // 5. 递归构建右子树
        // 前序右子树: [preLeft + 1 + leftSize, preRight)
        // 解释：从左子树结束的地方开始，直到当前区间结束
        // 中序右子树: [inRootIndex + 1, inRight)
        root.right = buildHelper(
            preLeft + 1 + leftSize,
            preRight,
            inRootIndex + 1,
            inRight
        );

        return root;
    }
}