跳到主要内容

二叉树算法练习

二叉树（Binary Tree）是面试频率最高的分类之一。考察重点包括：递归（DFS）、迭代（队列/栈）、层序遍历（BFS）以及二叉搜索树（BST）的性质。

94. 二叉树的中序遍历 (Binary Tree Inorder Traversal)​

题目描述​

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

解题思路​

中序遍历顺序：左子树 -> 根节点 -> 右子树。可以使用递归或基于栈的迭代法。

Java 代码实现​

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        helper(root, res);
        return res;
    }
    private void helper(TreeNode node, List<Integer> res) {
        if (node == null) return;
        helper(node.left, res);
        res.add(node.val);
        helper(node.right, res);
    }
}

104. 二叉树的最大深度 (Maximum Depth of Binary Tree)​

题目描述​

给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

解题思路​

典型的分治递归思路。最大深度 = max(leftDepth, rightDepth) + 1。

Java 代码实现​

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

226. 翻转二叉树 (Invert Binary Tree)​

题目描述​

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

解题思路​

递归地交换每个节点的左右子树。

Java 代码实现​

class Solution {
    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;
    }
}

101. 对称二叉树 (Symmetric Tree)​

题目描述​

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

解题思路​

递归判断：左树的左等于右树的右，左树的右等于右树的左。

Java 代码实现​

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

543. 二叉树的直径 (Diameter of Binary Tree)​

题目描述​

给你一棵二叉树的根节点 root，返回该树的 直径 。 直径 是任意两个节点路径长度中的最大值。这条路径可能穿过也可能不穿过根节点。

解题思路​

在计算深度的过程中，同步更新 max(leftHeight + rightHeight)。

Java 代码实现​

class Solution {
    int maxRes = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        depth(root);
        return maxRes;
    }
    private int depth(TreeNode node) {
        if (node == null) return 0;
        int L = depth(node.left);
        int R = depth(node.right);
        maxRes = Math.max(maxRes, L + R);
        return Math.max(L, R) + 1;
    }
}

102. 二叉树的层序遍历 (Binary Tree Level Order Traversal)​

题目描述​

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

解题思路​

使用队列实现 BFS。每次记录队列当前的长度 size，表示这一层的元素个数。

Java 代码实现​

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) return res;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> level = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                level.add(node.val);
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
            res.add(level);
        }
        return res;
    }
}

108. 将有序数组转换为二叉搜索树 (Convert Sorted Array to Binary Search Tree)​

题目描述​

给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。

解题思路​

取有序数组的中点作为根节点，递归处理左右半部分。

Java 代码实现​

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return build(nums, 0, nums.length - 1);
    }
    private TreeNode build(int[] nums, int L, int R) {
        if (L > R) return null;
        int mid = (L + R) / 2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = build(nums, L, mid - 1);
        root.right = build(nums, mid + 1, R);
        return root;
    }
}

98. 验证二叉搜索树 (Validate Binary Search Tree)​

题目描述​

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树（BST）。

解题思路​

BST 的中序遍历结果必然是严格递增的。或者使用递归法，向下传递可接受的上下界区间 [min, max]。

Java 代码实现​

class Solution {
    public boolean isValidBST(TreeNode root) {
        return isValid(root, null, null);
    }
    private boolean isValid(TreeNode root, Integer min, Integer max) {
        if (root == null) return true;
        if (min != null && root.val <= min) return false;
        if (max != null && root.val >= max) return false;
        return isValid(root.left, min, root.val) && isValid(root.right, root.val, max);
    }
}

230. 二叉搜索树中第 K 小的元素 (Kth Smallest Element in a BST)​

题目描述​

给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 个最小元素（从 1 开始计数）。

解题思路​

利用中序遍历的有序性。遍历到第 k 个元素即为答案。

Java 代码实现​

class Solution {
    int res, count;
    public int kthSmallest(TreeNode root, int k) {
        count = k; inorder(root);
        return res;
    }
    private void inorder(TreeNode root) {
        if (root == null) return;
        inorder(root.left);
        if (--count == 0) {
            res = root.val; return;
        }
        inorder(root.right);
    }
}

199. 二叉树的右视图 (Binary Tree Right Side View)​

题目描述​

给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

解题思路​

层序遍历（BFS），取每一层的最后一个元素。或者使用 DFS 优先访问右子树，记录每一层第一个被访问到的节点。

Java 代码实现​

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) return res;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (i == size - 1) res.add(node.val);
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
        }
        return res;
    }
}

114. 二叉树展开为链表 (Flatten Binary Tree to Linked List)​

题目描述​

给你二叉树的根节点 root ，请你将它展开为一个单链表。展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个节点，而左子指针始终为 null 。

解题思路​

前序遍历的变体。或者采取：对于每个节点，如果其有左子树，将左子树整体搬移到右边，而原来的右子树接到搬移后的最右节点下面。

Java 代码实现​

class Solution {
    public void flatten(TreeNode root) {
        while (root != null) {
            if (root.left != null) {
                TreeNode pre = root.left;
                while (pre.right != null) pre = pre.right;
                pre.right = root.right;
                root.right = root.left;
                root.left = null;
            }
            root = root.right;
        }
    }
}

105. 从前序与中序遍历序列构造二叉树 (Construct Binary Tree from Preorder and Inorder Traversal)​

题目描述​

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

解题思路​

前序数组的第一个元素即为根节点。在中序数组中找到该根节点的位置，从而确定左子树和右子树的节点数量。递归建树。

Java 代码实现​

class Solution {
    private Map<Integer, Integer> indexMap;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        indexMap = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) indexMap.put(inorder[i], i);
        return build(preorder, 0, preorder.length - 1, 0, inorder.length - 1);
    }
    private TreeNode build(int[] preorder, int pL, int pR, int iL, int iR) {
        if (pL > pR) return null;
        int rootVal = preorder[pL];
        int rootIndex = indexMap.get(rootVal);
        int leftLen = rootIndex - iL;
        TreeNode root = new TreeNode(rootVal);
        root.left = build(preorder, pL + 1, pL + leftLen, iL, rootIndex - 1);
        root.right = build(preorder, pL + leftLen + 1, pR, rootIndex + 1, iR);
        return root;
    }
}

437. 路径总和 III (Path Sum III)​

题目描述​

给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该树中路径和等于 targetSum 的 路径 的数目。路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的。

解题思路​

使用前缀和 + 哈希表优化。在递归遍历树的过程中，记录从根节点到当前节点的路径和，查询哈希表中是否存在 currSum - targetSum。

Java 代码实现​

class Solution {
    public int pathSum(TreeNode root, int targetSum) {
        Map<Long, Integer> prefix = new HashMap<>();
        prefix.put(0L, 1);
        return dfs(root, prefix, 0, targetSum);
    }
    private int dfs(TreeNode node, Map<Long, Integer> prefix, long currSum, int targetSum) {
        if (node == null) return 0;
        currSum += node.val;
        int res = prefix.getOrDefault(currSum - targetSum, 0);
        prefix.put(currSum, prefix.getOrDefault(currSum, 0) + 1);
        res += dfs(node.left, prefix, currSum, targetSum);
        res += dfs(node.right, prefix, currSum, targetSum);
        prefix.put(currSum, prefix.get(currSum) - 1);
        return res;
    }
}

236. 二叉树的最近公共祖先 (Lowest Common Ancestor of a Binary Tree)​

题目描述​

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先 (LCA)。 最近公共祖先的定义为：对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大。

解题思路​

递归。如果当前节点等于 p 或 q，直接返回当前节点。否则去左右子树寻找。

  1. 如果左右子树各回传了一个非空值，说明 p, q 分布在当前节点两侧，当前节点即为 LCA。
  2. 否则 LCA 位于回传了非空值的那一侧。

Java 代码实现​

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) return root;
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if (left == null) return right;
        if (right == null) return left;
        return root;
    }
}

124. 二叉树中的最大路径和 (Binary Tree Maximum Path Sum)​

题目描述​

路径被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点。本题要求返回最大路径和。

解题思路​

对于每个节点，计算以其为顶点的“拱形”路径和：leftGain + rightGain + node.val。同时向父节点返回该节点能贡献的最大“单边”收益：node.val + max(leftGain, rightGain)。

Java 代码实现​

class Solution {
    int maxSum = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        gain(root);
        return maxSum;
    }
    private int gain(TreeNode node) {
        if (node == null) return 0;
        int left = Math.max(gain(node.left), 0);
        int right = Math.max(gain(node.right), 0);
        maxSum = Math.max(maxSum, node.val + left + right);
        return node.val + Math.max(left, right);
    }
}