Leetcode 0637. Average of Levels in Binary Tree
637. Average of Levels in Binary TreeGiven the root of a binary tree, return the average value of the nodes on each level in the form of an array. Answers within 10-5 of the actual answer will be accepted. Example 1: 1234Input: root = [3,9,20,null,null,15,7]Output: [3.00000,14.50000,11.00000]Explanation: The average value of nodes on level 0 is 3, on level 1 is 14.5, and on level 2 is 11.Hence return [3, 14.5, 11]. Example 2: 12Input: root = [3,9,20,15,7]Output: [3.00000,14.50000,11.00000...
Leetcode 0572. Subtree of Another Tree
572. Subtree of Another TreeGiven the roots of two binary trees root and subRoot, return true if there is a subtree of root with the same structure and node values of subRoot and false otherwise. A subtree of a binary tree tree is a tree that consists of a node in tree and all of this node's descendants. The tree tree could also be considered as a subtree of itself. Example 1: 12Input: root = [3,4,5,1,2], subRoot = [4,1,2]Output: true Example 2: 12Input: root = [3,4,5,1,2,null,null,nu...
Leetcode 0515. Find Largest Value in Each Tree Row
515. Find Largest Value in Each Tree RowGiven the root of a binary tree, return an array of the largest value in each row of the tree (0-indexed). Example 1: 12Input: root = [1,3,2,5,3,null,9]Output: [1,3,9] Example 2: 12Input: root = [1,2,3]Output: [1,3] 题目大意给定一棵二叉树的根节点 root，返回一个数组，其中每个元素是二叉树对应行（从 0 开始索引）中的最大值。 例如： 输入二叉树 [1,3,2,5,3,null,9]，第 0 行最大值为 1，第 1 行最大值为 3，第 2 行最大值为 9，因此返回 [1,3,9]。 解题思路要找到每一行的最大值，核心是按层遍历二叉树，并在遍历过程中记录每层的最大值。具体步骤如下： 层序遍历初始化：若根节点为空，直接返回空数组；否则将根节点入队。 逐层处理节点： 记录当前队列...
Leetcode 0513. Find Bottom Left Tree Value
513. Find Bottom Left Tree ValueGiven the root of a binary tree, return the leftmost value in the last row of the tree. Example 1: 12Input: root = [2,1,3]Output: 1 Example 2: 12Input: root = [1,2,3,4,null,5,6,null,null,7]Output: 7 题目大意给定一棵二叉树的根节点 root，返回树的最后一行中最左边的节点值。即需要找到二叉树最深一层的最左侧节点的值。 例如： 输入二叉树 [2,1,3]，最深层是第 2 层，最左侧节点值为 1，返回 1； 输入二叉树 [1,2,3,4,null,5,6,null,null,7]，最深层是第 4 层，最左侧节点值为 7，返回 7。 解题思路找到树左下角的值，关键是确定最深层和该层的最左侧节点。主要有两种实现方法： 1. 层序遍历（BFS） 按层遍历二叉树，记录每一层的第一个节点值； 最后一层的第一个节点值即为结果...
Leetcode 0429. N-ary Tree Level Order Traversal
429. N-ary Tree Level Order TraversalGiven an n-ary tree, return the level order traversal of its nodes' values. Nary-Tree input serialization is represented in their level order traversal, each group of children is separated by the null value (See examples). Example 1: 12Input: root = [1,null,3,2,4,null,5,6]Output: [[1],[3,2,4],[5,6]] Example 2: 12Input: root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]Output: [[1],[2,3,4,5],[6,7,8,9,10]...
Leetcode 0404. Sum of Left Leaves
404. Sum of Left LeavesGiven the root of a binary tree, return the sum of all left leaves. A leaf is a node with no children. A left leaf is a leaf that is the left child of another node. Example 1: 123Input: root = [3,9,20,null,null,15,7]Output: 24Explanation: There are two left leaves in the binary tree, with values 9 and 15 respectively. Example 2: 12Input: root = [1]Output: 0 题目大意给定一棵二叉树的根节点 root，返回所有左叶子的节点值之和。左叶子的定义是：既是叶子节点（没有子节点），又是其父节点的左子节点。 例如： 输入二叉树 [3,9,20,null,null,15,7]，左叶子为 ...
Leetcode 0257. Binary Tree Paths
257. Binary Tree PathsGiven the root of a binary tree, return all root-to-leaf paths in any order. A leaf is a node with no children. Example 1: 12Input: root = [1,2,3,null,5]Output: ["1->2->5","1->3"] Example 2: 12Input: root = [1]Output: ["1"] 题目大意给定一棵二叉树的根节点 root，返回所有从根节点到叶子节点的路径。叶子节点是指没有子节点的节点，路径以字符串形式表示，节点值之间用 "->" 连接。 例如： 输入二叉树 [1,2,3,null,5]，根到叶子的路径为 1->2->5 和 1->3，返回 ["1->2->5","1->3"]。 解题思...
Leetcode 0226. Invert Binary Tree
226. Invert Binary TreeGiven the root of a binary tree, invert the tree, and return its root. Example 1: 12Input: root = [4,2,7,1,3,6,9]Output: [4,7,2,9,6,3,1] Example 2: 12Input: root = [2,1,3]Output: [2,3,1] Example 3: 12Input: root = []Output: [] 题目大意给定一棵二叉树的根节点 root，翻转这棵二叉树（即交换每个节点的左子树和右子树），并返回翻转后的根节点。 例如： 输入二叉树 [4,2,7,1,3,6,9]，翻转后每个节点的左右子树互换，输出为 [4,7,2,9,6,3,1]。 解题思路翻转二叉树的核心是交换每个节点的左子节点和右子节点，可以通过递归或迭代两种方式实现： 1. 递归法利用二叉树的递归性质： 若当前节点为空，直接返回； 否则，先交换当前节点的左、右子节点； 递归翻转当前节点的左子树和右子树。 2...
Leetcode 0222. Count Complete Tree Nodes
222. Count Complete Tree NodesGiven the root of a complete binary tree, return the number of the nodes in the tree. According to Wikipedia, every level, except possibly the last, is completely filled in a complete binary tree, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h. Design an algorithm that runs in less than O(n) time complexity. Example 1: 12Input: root = [1,2,3,4,5,6]Output: 6 Example 2: 12Input: root ...
Leetcode 0199. Binary Tree Right Side View
199. Binary Tree Right Side ViewGiven the root of a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom. Example 1: Input: root = [1,2,3,null,5,null,4] Output: [1,3,4] Explanation: Example 2: Input: root = [1,2,3,4,null,null,null,5] Output: [1,3,4,5] Explanation: Example 3: Input: root = [1,null,3] Output: [1,3] Example 4: Input: root = [] Output: [] 题目大意给定一棵二叉树的根节点 root，想象自己站在树的右侧，返回从顶部到底...
Leetcode 0145. Binary Tree Postorder Traversal
145. Binary Tree Postorder TraversalGiven the root of a binary tree, return the postorder traversal of its nodes' values. Example 1: Input: root = [1,null,2,3] Output: [3,2,1] Explanation: Example 2: Input: root = [1,2,3,4,5,null,8,null,null,6,7,9] Output: [4,6,7,5,2,9,8,3,1] Explanation: Example 3: Input: root = [] Output: [] Example 4: Input: root = [1] Output: [1] 题目大意给定一棵二叉树的根节点 root，返回其节点值的后序遍历结果。后序遍历的顺序是「左子树 → 右子树 → 根节点」，遵循 "左 - 右 - 根" 的递归逻辑。 解题思路后序遍...
Leetcode 0144. Binary Tree Preorder Traversal
144. Binary Tree Preorder TraversalGiven the root of a binary tree, return the preorder traversal of its nodes' values. Example 1: Input: root = [1,null,2,3] Output: [1,2,3] Explanation: Example 2: Input: root = [1,2,3,4,5,null,8,null,null,6,7,9] Output: [1,2,4,5,6,7,3,8,9] Explanation: Example 3: Input: root = [] Output: [] Example 4: Input: root = [1] Output: [1] 题目大意给定一棵二叉树的根节点 root，返回其节点值的前序遍历结果。前序遍历的顺序是「根节点 → 左子树 → 右子树」，遵循 "根 - 左 - 右" 的递归逻辑。 解题思路前序遍历的...
Leetcode 0116. Populating Next Right Pointers in Each Node
116. Populating Next Right Pointers in Each NodeYou are given a perfect binary tree where all leaves are on the same level, and every parent has two children. The binary tree has the following definition: 123456struct Node { int val; Node *left; Node *right; Node *next;} Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL. Initially, all next pointers are set to NULL. Example 1: 123Input: root = [1...
Leetcode 0112. Path Sum
112. Path SumGiven the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum. A leaf is a node with no children. Example 1: 123Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22Output: trueExplanation: The root-to-leaf path with the target sum is shown. Example 2: 123456Input: root = [1,2,3], targetSum = 5Output: falseExplanation: There are two root-to-leaf pat...
Leetcode 0110. Balanced Binary Tree
110. Balanced Binary TreeGiven a binary tree, determine if it is height-balanced. Example 1: 12Input: root = [3,9,20,null,null,15,7]Output: true Example 2: 12Input: root = [1,2,2,3,3,null,null,4,4]Output: false Example 3: 12Input: root = []Output: true 题目大意给定一棵二叉树，判断它是否是高度平衡的。高度平衡平衡二叉树 ** 的定义是：二叉树的每个节点的左右两个子树的高度差的绝对值不超过 1。 例如： 输入二叉树 [3,9,20,null,null,15,7]，每个节点的左右子树高度差均不超过 1，返回 true； 输入二叉树 [1,2,2,3,3,null,null,4,4]，根节点的左子树高度为 3，右子树高度为 1，差为 2，返回 false。 解题思路判断平衡二叉树的核心是计算每个节点的左右子树高度，并检查高...
Leetcode 0108. Convert Sorted Array to Binary Search Tree
108. Convert Sorted Array to Binary Search TreeGiven an integer array nums where the elements are sorted in ascending order, convert it to a *height-balanced* binary search tree. Example 1: 123Input: nums = [-10,-3,0,5,9]Output: [0,-3,9,-10,null,5]Explanation: [0,-10,5,null,-3,null,9] is also accepted: Example 2: 123Input: nums = [1,3]Output: [3,1]Explanation: [1,null,3] and [3,1] are both height-balanced BSTs. 题目大意给定一个升序排列的整数数组 nums，将其转换为一棵高度平衡的二叉搜索树（BST）。高度平衡的定义是：二叉树的左右两个子树的高度差的绝对值不超过 ...
Leetcode 0107. Binary Tree Level Order Traversal II
107. Binary Tree Level Order Traversal IIGiven the root of a binary tree, return the bottom-up level order traversal of its nodes' values. (i.e., from left to right, level by level from leaf to root). Example 1: 12Input: root = [3,9,20,null,null,15,7]Output: [[15,7],[9,20],[3]] Example 2: 12Input: root = [1]Output: [[1]] Example 3: 12Input: root = []Output: [] 题目大意给定一棵二叉树的根节点 root，返回其节点值的自底向上的层序遍历结果。即按「从叶子节点所在层到根节点所在层」的顺序逐层返回，每层内部仍保持「从左到右」的顺序。 例如： 输入二叉树 [3,9,20,null,null,15,7]，其自底向上...
Leetcode 0106. Construct Binary Tree from Inorder and Postorder Traversal
106. Construct Binary Tree from Inorder and Postorder TraversalGiven two integer arrays inorder and postorder where inorder is the inorder traversal of a binary tree and postorder is the postorder traversal of the same tree, construct and return the binary tree. Example 1: 12Input: inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]Output: [3,9,20,null,null,15,7] Example 2: 12Input: inorder = [-1], postorder = [-1]Output: [-1] 题目大意给定一棵二叉树的中序遍历数组 inorder 和后序遍历数组 postorder，请构造并返回这棵二叉树。 例如： ...
Leetcode 0104. Maximum Depth of Binary Tree
104. Maximum Depth of Binary TreeGiven the root of a binary tree, return its maximum depth. A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node. Example 1: 12Input: root = [3,9,20,null,null,15,7]Output: 3 Example 2: 12Input: root = [1,null,2]Output: 2 题目大意给定一棵二叉树的根节点 root，返回该二叉树的最大深度。二叉树的最大深度是指从根节点到最远叶子节点的最长路径上的节点数量。 例如： 输入二叉树 [3,9,20,null,null,15,7]，其最大深度为 3（路径：3 → 20 → 15 或 3 → 20 → 7，均包含 3 个节点）。 解题思路计算二叉树的最...
Leetcode 0103. Binary Tree Zigzag Level Order Traversal
103. Binary Tree Zigzag Level Order Traversal Given the root of a binary tree, return the zigzag level order traversal of its nodes' values. (i.e., from left to right, then right to left for the next level and alternate between). Example 1: 12Input: root = [3,9,20,null,null,15,7]Output: [[3],[20,9],[15,7]] Example 2: 12Input: root = [1]Output: [[1]] Example 3: 12Input: root = []Output: [] 题目大意给定一棵二叉树的根节点，返回其节点值的锯齿形层序遍历。即：第一层从左到右，第二层从右到左，第三层再从左到右，以此类推，交替进行。 例如： 输入 root = [3,9,20,null...
Leetcode 0101. Symmetric Tree
101. Symmetric TreeGiven the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center). Example 1: 12Input: root = [1,2,2,3,4,4,3]Output: true Example 2: 12Input: root = [1,2,2,null,3,null,3]Output: false 题目大意给定一棵二叉树的根节点 root，判断该二叉树是否是对称的（即围绕中心轴镜像对称）。 例如： 输入二叉树 [1,2,2,3,4,4,3]，其左子树与右子树成镜像，故返回 true； 输入二叉树 [1,2,2,null,3,null,3]，左子树与右子树不镜像，故返回 false。 解题思路判断二叉树是否对称的核心是比较左子树与右子树是否成镜像，即： 左子树的左节点需与右子树的右节点值相等； 左子树的右节点需与右子树的左节点值相等。 1. 递归法设计一个辅助函数，比较两个子树...
Leetcode 0100. Same Tree
100. Same TreeGiven the roots of two binary trees p and q, write a function to check if they are the same or not. Two binary trees are considered the same if they are structurally identical, and the nodes have the same value. Example 1: 12Input: p = [1,2,3], q = [1,2,3]Output: true Example 2: 12Input: p = [1,2], q = [1,null,2]Output: false Example 3: 12Input: p = [1,2,1], q = [1,1,2]Output: false 题目大意给定两棵二叉树的根节点 p 和 q，判断这两棵树是否相同。两棵树相同的定义是：结构完全相同，且对应节点的值也相同。 例如： 输入两棵结构和节点值均相同的树 [1,2,3]...
Leetcode 0099. Recover Binary Search Tree
99. Recover Binary Search TreeYou are given the root of a binary search tree (BST), where the values of exactly two nodes of the tree were swapped by mistake. Recover the tree without changing its structure. Example 1: 123Input: root = [1,3,null,null,2]Output: [3,1,null,null,2]Explanation: 3 cannot be a left child of 1 because 3 > 1. Swapping 1 and 3 makes the BST valid. Example 2: 123Input: root = [3,1,4,null,null,2]Output: [2,1,4,null,null,3]Explanation: 2 cannot be in the right subt...
Leetcode 0098. Validate Binary Search Tree
98. Validate Binary Search TreeGiven the root of a binary tree, determine if it is a valid binary search tree (BST). A valid BST is defined as follows: The left subtree of a node contains only nodes with keys strictly less than the node's key. The right subtree of a node contains only nodes with keys strictly greater than the node's key. Both the left and right subtrees must also be binary search trees. Example 1: 12Input: root = [2,1,3]Output: true Example 2: 123Input: root = [...
Leetcode 0096. Unique Binary Search Trees
96. Unique Binary Search TreesGiven an integer n, return *the number of structurally unique **BST'*s (binary search trees) which has exactly n nodes of unique values from 1 to n. Example 1: 12Input: n = 3Output: 5 Example 2: 12Input: n = 1Output: 1 题目大意给定一个整数 n，计算由 1 到 n 为节点所组成的结构独特的二叉搜索树（BST）的数量。 例如： 输入 n = 3，存在 5 种结构独特的 BST，返回 5； 输入 n = 1，只有 1 种 BST，返回 1。 解题思路计算独特 BST 的数量可以通过动态规划（DP） 实现，核心思路基于以下观察： 若选择 i 作为根节点，则左子树由 1~i-1 构成，右子树由 i+1~n 构成； 左子树的独特结构数量为 dp[i-1]，右子树的独特结构数量为 dp[n-i]（...
