跳到主要内容

二叉树

二叉树的核心思想在于递归。利用前、中、后序遍历的特性解决问题。

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

题目描述​

给定一个二叉树的根节点 root ，返回其 最大深度 。

二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。

解题思路​

分治/递归。

  1. maxDepth(root) = 1 + max(maxDepth(root.left), maxDepth(root.right))。
  2. 基础条件：root == null 返回 0。

Java 代码实现​

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

100. 相同的树 (Same Tree)​

题目描述​

给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

解题思路​

深度优先搜索 (DFS)。

  1. 两根都空：相同。
  2. 一空一非空：不同。
  3. 两根非空：值相等且左子树相同且右子树相同。

Java 代码实现​

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

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

题目描述​

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

解题思路​

递归后序或前序。

  1. 递归翻转左子树。
  2. 递归翻转右子树。
  3. 交换当前节点的左右指针。

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 ， 检查它是否轴对称。

解题思路​

递归双树比较。

  1. 定义外部辅助函数 isMirror(T1, T2)。
  2. T1.val == T2.val。
  3. isMirror(T1.left, T2.right) 且 isMirror(T1.right, T2.left)。

Java 代码实现​

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

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

题目描述​

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

解题思路​

根节点位置拆分。

  1. 前序遍历的第一个节点一定是根节点。
  2. 在中序遍历中通过哈希表找到该根节点的位置，中序遍历中根节点左边的就是左子树，右边的就是右子树。
  3. 递归构造左右子树。

Java 代码实现​

class Solution {
    Map<Integer, Integer> map = new HashMap<>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        for (int i = 0; i < inorder.length; i++) map.put(inorder[i], i);
        return build(preorder, 0, preorder.length - 1, 0);
    }
    private TreeNode build(int[] pre, int preL, int preR, int inL) {
        if (preL > preR) return null;
        TreeNode node = new TreeNode(pre[preL]);
        int mid = map.get(pre[preL]);
        int leftSize = mid - inL;
        node.left = build(pre, preL + 1, preL + leftSize, inL);
        node.right = build(pre, preL + leftSize + 1, preR, mid + 1);
        return node;
    }
}

112. 路径总和 (Path Sum)​

题目描述​

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 从根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。

叶子节点 是指没有子节点的节点。

解题思路​

递归减去当前值。

  1. 叶子节点判断：root.left == null && root.right == null && root.val == sum。
  2. 基础情况：root == null 返回 false。
  3. 递归：hasPath(root.left, sum - root.val) || hasPath(root.right, sum - root.val)。

Java 代码实现​

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

222. 完全二叉树的节点个数 (Count Complete Tree Nodes)​

题目描述​

给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。

完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2^h 个节点。

解题思路​

利用完全性进行二分。

  1. 沿左侧和右侧计算左右高度。
  2. 如果相等，则为满二叉树，节点数为 2^h - 1。
  3. 如果不等，递归。

Java 代码实现​

class Solution {
    public int countNodes(TreeNode root) {
        if (root == null) return 0;
        int l = height(root.left), r = height(root.right);
        if (l == r) return (1 << l) + countNodes(root.right);
        else return (1 << r) + countNodes(root.left);
    }
    private int height(TreeNode root) {
        int h = 0;
        while (root != null) { h++; root = root.left; }
        return h;
    }
}

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

题目描述​

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

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

解题思路​

后序遍历回传节点。

  1. 只要当前点是 p 或 q 或空，直接返回。
  2. 递归查找左右子树。
  3. 如果左右返回都不空，当前点即为 LCA。
  4. 否则返回那个非空的子树返回值。

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 && right != null) return root;
        return left != null ? left : right;
    }
}

106. 从中序与后序遍历序列构造二叉树 (Construct Binary Tree from Inorder and Postorder Traversal)​

题目描述​

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

解题思路​

后序末尾确定根节点。

  1. 后序遍历最后一个元素为根。
  2. 在中序遍历中定位根，划分左右子树。
  3. 递归构建右子树，再构建左子树（因为后序遍历顺着往前是：根、右、左）。

Java 代码实现​

class Solution {
    int posIndex;
    Map<Integer, Integer> map = new HashMap<>();
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        posIndex = postorder.length - 1;
        for (int i = 0; i < inorder.length; i++) map.put(inorder[i], i);
        return build(postorder, 0, inorder.length - 1);
    }
    private TreeNode build(int[] post, int left, int right) {
        if (left > right) return null;
        int val = post[posIndex--];
        TreeNode root = new TreeNode(val);
        int mid = map.get(val);
        root.right = build(post, mid + 1, right);
        root.left = build(post, left, mid - 1);
        return root;
    }
}

117. 填充每个节点的下一个右侧节点指针 II (Populating Next Right Pointers in Each Node II)​

题目描述​

给定一个二叉树：

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL 。

初始状态下，所有 next 指针都被设置为 NULL 。

解题思路​

利用已建立的 next 指针进行层序遍历。

  1. 每一层维护一个 dummy 节点。
  2. 遍历当前层时，通过 next 指针将下一层的节点串联起来。
  3. 处理完一层后，跳到下一层的首节点。

Java 代码实现​

class Solution {
    public Node connect(Node root) {
        Node cur = root;
        while (cur != null) {
            Node dummy = new Node(0), p = dummy;
            while (cur != null) {
                if (cur.left != null) { p.next = cur.left; p = p.next; }
                if (cur.right != null) { p.next = cur.right; p = p.next; }
                cur = cur.next;
            }
            cur = dummy.next;
        }
        return root;
    }
}

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

题目描述​

给你二叉树的根节点 root ，请你将它展开为一个单链表：

  • 展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个节点，而左子指针始终为 null 。
  • 展开后的单链表应该与二叉树 先序遍历 顺序相同。

解题思路​

原左子树插入右侧。

  1. 对于当前节点，如果左子树不为空，找到左子树最右边的节点 pre。
  2. 将 root.right 接到 pre.right。
  3. 将 root.right 更新为 root.left，并将 root.left 置空。
  4. 处理下一个节点（原本的右子树或新的右子树）。

Java 代码实现​

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

129. 求根节点到叶节点数字之和 (Sum Root to Leaf Numbers)​

题目描述​

给你一个二叉树的根节点 root ，树中每个节点都存放有一个 0 到 9 之间的数字。

每条从根节点到叶节点的路径都代表一个数字：

  • 例如，从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123 。

计算从根节点到叶节点生成的 所有数字之和 。

叶节点 是指没有子节点的节点。

解题思路​

路径值累加。

  1. 递归过程中传递 currentSum * 10 + root.val。
  2. 只有到叶子节点时才返回该值。

Java 代码实现​

class Solution {
    public int sumNumbers(TreeNode root) {
        return dfs(root, 0);
    }
    private int dfs(TreeNode node, int sum) {
        if (node == null) return 0;
        sum = sum * 10 + node.val;
        if (node.left == null && node.right == null) return sum;
        return dfs(node.left, sum) + dfs(node.right, sum);
    }
}

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

题目描述​

二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。

路径和 是路径中各节点值的总和。

给你一个二叉树的根节点 root ，返回其 最大路径和 。

解题思路​

向上传递最大单侧贡献值。

  1. 定义递归函数计算节点能向父节点提供的最大值：root.val + max(0, leftContribution, rightContribution)。
  2. 在递归过程中更新全局最大值：totalSum = root.val + max(0, left) + max(0, right)。

Java 代码实现​

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

173. 二叉搜索树迭代器 (Binary Search Tree Iterator)​

题目描述​

实现一个二叉搜索树迭代器类 BSTIterator ，表示一个按中序遍历二叉搜索树（BST）的迭代器：

  • BSTIterator(TreeNode root) 初始化 BSTIterator 类的一个对象。BST 的根节点 root 会作为构造函数的一部分给出。指针应初始化为一个不存在于 BST 中的最小数，且应小于 BST 中的任何元素。
  • boolean hasNext() 如果向指针右侧遍历存在数字，则返回 true ；否则返回 false 。
  • int next() 将指针向右移动，然后返回指针处的数字。

注意，指针初始化为一个不存在于 BST 中的最小数，所以第一次调用 next() 将返回 BST 中的最小元素。

你可以假设 next() 调用总是有效的，也就是说，当调用 next() 时，BST 的中序遍历中至少存在一个下一个数字。

解题思路​

受控的中序遍历栈。

  1. 初始化时将根节点及所有左后代节点压入栈。
  2. next()：弹出栈顶元素，如果该元素有右子树，将右子树及所有其左后代压入栈。

Java 代码实现​

class BSTIterator {
    Deque<TreeNode> stack = new ArrayDeque<>();
    public BSTIterator(TreeNode root) {
        pushAll(root);
    }
    public int next() {
        TreeNode node = stack.pop();
        pushAll(node.right);
        return node.val;
    }
    public boolean hasNext() {
        return !stack.isEmpty();
    }
    private void pushAll(TreeNode node) {
        while (node != null) {
            stack.push(node);
            node = node.left;
        }
    }
}