本文解决的问题: 按主题归纳 二叉树 相关高频题型与通用解法。

适用范围: LeetCode 中文站题目,示例主要使用 Java。

阅读建议: 先识别数据结构与不变量,再结合题目约束选择算法,不要只记忆代码。

二叉树

二叉树的中序遍历(简单)

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

进阶: 递归算法很简单,你可以通过迭代算法完成吗?

提示:
树中节点数目在范围 [0, 100] 内

100 <= Node.val <= 100

示例:
![1. 二叉树的中序遍历 (简)示例](/img/leetcode/image 33.png)

1
2
输入:root = [1,null,2,3]
输出:[1,3,2]

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
/**
* Definition for a binary tree node.
* public 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;
* }
* }
*/
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();

// 边界条件检查
if (root == null) {
return res;
}

TreeNode current = root;

while (current != null) {
if (current.left == null) {
// 当前节点没有左子树,直接访问当前节点并移动到右子树
res.add(current.val);
current = current.right;
} else {
// 找到当前节点左子树的最右节点
TreeNode predecessor = current.left;
while (predecessor.right != null && predecessor.right != current) {
predecessor = predecessor.right;
}

if (predecessor.right == null) {
// 建立临时链接
predecessor.right = current;
current = current.left;
} else {
// 已经建立过临时链接,现在移除它并访问当前节点
predecessor.right = null;
res.add(current.val);
current = current.right;
}
}
}

return res;
}
}

二叉树的最大深度(简单)

给定一个二叉树 root ,返回其最大深度。

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

提示:
树中节点的数量在 [0, 104] 区间内。

100 <= Node.val <= 100

示例:
![2. 二叉树的最大深度 (简)示例](/img/leetcode/image 34.png)

1
2
输入:root = [3,9,20,null,null,15,7]
输出:3

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
// 深度优先搜索算法
/**
* Definition for a binary tree node.
* public 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;
* }
* }
*/
class Solution {
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
} else {
int leftHeight = maxDepth(root.left);
int rightHeight = maxDepth(root.right);
return Math.max(leftHeight, rightHeight) + 1;
}
}
}

// 广度优先搜索算法
class Solution {
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
int ans = 0;
while (!queue.isEmpty()) {
int size = queue.size();
while (size > 0) {
TreeNode node = queue.poll();
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
size--;
}
ans++;
}
return ans;
}
}

二叉搜索树中第 K 小的元素(简单)

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

提示:

  • 树中的节点数为 n 。
  • 1 <= k <= n <= 104
  • 0 <= Node.val <= 104

示例:
3. 二叉搜索树中第 K 小的元素 (简)示例

1
2
输入:root = [3,1,4,null,2], k = 1
输出:1

3. 二叉搜索树中第 K 小的元素 (简)示例

1
2
输入:root = [5,3,6,2,4,null,null,1], k = 3
输出:3

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int kthSmallest(TreeNode root, int k) {
Deque<TreeNode> stack = new ArrayDeque<TreeNode>();
while (root != null || !stack.isEmpty()) {
while (root != null) {
stack.push(root);
root = root.left;
}
root = stack.pop();
--k;
if (k == 0) {
break;
}
root = root.right;
}
return root.val;
}

翻转二叉树(简单)

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

提示:

  • 树中节点数目范围在 [0, 100] 内
  • -100 <= Node.val <= 100

示例 1:

4. 翻转二叉树 (简)示例

1
2
输入:root = [4,2,7,1,3,6,9]
输出:[4,7,2,9,6,3,1]

示例 2:

4. 翻转二叉树 (简)示例

1
2
输入:root = [2,1,3]
输出:[2,3,1]

示例 3:

1
2
输入:root = []
输出:[]

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
* Definition for a binary tree node.
* public 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;
* }
* }
*/
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;
}
}

二叉树的层序遍历(中等)

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

提示:

  • 树中节点数目在范围 [0, 2000] 内
  • -1000 <= Node.val <= 1000

示例:

1
2
3
4
5
6
7
8
9
10
输入:root = [3,9,20,null,null,15,7]
输出:[[3],[9,20],[15,7]]

示例 2:
输入:root = [1]
输出:[[1]]

示例 3:
输入:root = []
输出:[]

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> ret = new ArrayList<List<Integer>>();
if (root == null) {
return ret;
}

Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
while (!queue.isEmpty()) {
List<Integer> level = new ArrayList<Integer>();
int currentLevelSize = queue.size();
for (int i = 1; i <= currentLevelSize; ++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);
}
}
ret.add(level);
}

return ret;
}

验证二叉搜索树(中等)

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

有效 二叉搜索树定义如下:

  • 节点的左子树只包含 小于 当前节点的数。
  • 节点的右子树只包含 大于 当前节点的数。
  • 所有左子树和右子树自身必须也是二叉搜索树。

提示:

  • 树中节点数目范围在 [1, 104] 内
  • -231 <= Node.val <= 231 - 1

示例 1:

6. 验证二叉搜索树 (中)示例

1
2
输入:root = [2,1,3]
输出:true

示例 2:

6. 验证二叉搜索树 (中)示例

1
2
3
输入:root = [5,1,4,null,null,3,6]
输出:false
解释:根节点的值是 5 ,但是右子节点的值是 4 。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
public boolean isValidBST(TreeNode root) {
return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
}

private boolean isValidBST(TreeNode root, long min, long max) {
if (root == null) {
return true;
}
if (root.val <= min || root.val >= max) {
return false;
}
return isValidBST(root.left, min, root.val) && isValidBST(root.right, root.val, max);
}

验证二叉搜索树(中等)

有效 二叉搜索树定义如下:

  • 节点的左子树只包含** 小于 **当前节点的数。
  • 节点的右子树只包含 大于 当前节点的数。
  • 所有左子树和右子树自身必须也是二叉搜索树。

提示:

  • 树中节点数目在范围 [1, 1000] 内
  • -100 <= Node.val <= 100

进阶: 你可以运用递归和迭代两种方法解决这个问题吗?

示例 1:

7. 验证二叉搜索树 (中)示例

1
2
输入:root = [1,2,2,3,4,4,3]
输出:true

示例 2:

7. 验证二叉搜索树 (中)示例

1
2
输入:root = [1,2,2,null,3,null,3]
输出:false

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution {
public boolean isSymmetric(TreeNode root) {
return root == null || rece(root.left, root.right);
}

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



二叉树的直径(中等)

给你一棵二叉树的根节点,返回该树的 直径 。

二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。

两节点之间路径的 长度 由它们之间边数表示。

提示:

  • 树中节点数目在范围 [1, 10^4] 内
  • -100 <= Node.val <= 100

示例 1:

8. 二叉树的直径 (中)示例

1
2
3
输入:root = [1,2,3,4,5]
输出:3
解释:3 ,取路径 [4,2,1,3] 或 [5,2,1,3] 的长度。

示例 2:

1
2
输入:root = [1,2]
输出:1

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/**
* Definition for a binary tree node.
* public 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;
* }
* }
*/
class Solution {

int ans = 0;

public int diameterOfBinaryTree(TreeNode root) {
ans = 1;
dfs(root);
return ans - 1;
}

private int dfs(TreeNode root) {
if(root == null) {
return 0;
}
int l = dfs(root.left);
int r = dfs(root.right);
ans = Math.max(ans, l+r+1);
return Math.max(l, r) + 1;
}
}

将有序数组转换为二叉搜索树(中等)

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

提示:

  • 1 <= nums.length <= 10^4
  • -10^4 <= nums[i] <= 10^4
  • nums 按 严格递增 顺序排列

示例 1:

9. 将有序数组转换为二叉搜索树 (中)示例

1
2
3
4
输入:nums = [-10,-3,0,5,9]
输出:[0,-3,9,-10,null,5]
解释:[0,-10,5,null,-3,null,9] 也将被视为正确答案:
![9. 将有序数组转换为二叉搜索树示例](/img/leetcode/external/btree2.jpg)

示例 2:

9. 将有序数组转换为二叉搜索树 (中)示例

1
2
3
输入:nums = [1,3]
输出:[3,1]
解释:[1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/**
* Definition for a binary tree node.
* public 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;
* }
* }
*/
class Solution {
Random rand = new Random();

public TreeNode sortedArrayToBST(int[] nums) {
return helper(nums, 0, nums.length - 1);
}

public TreeNode helper(int[] nums, int left, int right) {
if (left > right) {
return null;
}

// 选择任意一个中间位置数字作为根节点
int mid = (left + right + rand.nextInt(2)) / 2;

TreeNode root = new TreeNode(nums[mid]);
root.left = helper(nums, left, mid - 1);
root.right = helper(nums, mid + 1, right);
return root;
}
}

二叉树的右视图(中等)

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

提示:

  • 二叉树的节点个数的范围是 [0,100]
  • -100 <= Node.val <= 100

示例 1:

输入: root = [1,2,3,null,5,null,4]

输出: [1,3,4]

解释:

10. 二叉树的右视图 (中)示例

示例 2:

输入: root = [1,2,3,4,null,null,null,5]

输出: [1,3,4,5]

解释:

10. 二叉树的右视图 (中)示例

示例 3:

输入: root = [1,null,3]

输出: [1,3]

示例 4:

输入: root = []

输出: []

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
public List<Integer> rightSideView(TreeNode root) {
Map<Integer, Integer> rightmostValueAtDepth = new HashMap<Integer, Integer>();
int max_depth = -1;

Deque<TreeNode> nodeStack = new LinkedList<TreeNode>();
Deque<Integer> depthStack = new LinkedList<Integer>();
nodeStack.push(root);
depthStack.push(0);

while (!nodeStack.isEmpty()) {
TreeNode node = nodeStack.pop();
int depth = depthStack.pop();

if (node != null) {
// 维护二叉树的最大深度
max_depth = Math.max(max_depth, depth);

// 如果不存在对应深度的节点我们才插入
if (!rightmostValueAtDepth.containsKey(depth)) {
rightmostValueAtDepth.put(depth, node.val);
}

nodeStack.push(node.left);
nodeStack.push(node.right);
depthStack.push(depth + 1);
depthStack.push(depth + 1);
}
}

List<Integer> rightView = new ArrayList<Integer>();
for (int depth = 0; depth <= max_depth; depth++) {
rightView.add(rightmostValueAtDepth.get(depth));
}

return rightView;
}
}

二叉树展开为链表(中等)

给你二叉树的根结点 root ,请你将它展开为一个单链表:

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

提示:

  • 树中结点数在范围 [0, 2000] 内
  • -100 <= Node.val <= 100

进阶: 你可以使用原地算法(O(1) 额外空间)展开这棵树吗?

示例 1:

11. 二叉树展开为链表 (中)示例

1
2
输入:root = [1,2,5,3,4,null,6]
输出:[1,null,2,null,3,null,4,null,5,null,6]

示例 2:

1
2
输入:root = []
输出:[]

示例 3:

1
2
输入:root = [0]
输出:[0]

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class Solution {
public void flatten(TreeNode root) {
List<TreeNode> list = new ArrayList<TreeNode>();
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);
}
}
}

// 以下代码通过迭代实现前序遍历。
class Solution {
public void flatten(TreeNode root) {
List<TreeNode> list = new ArrayList<TreeNode>();
Deque<TreeNode> stack = new LinkedList<TreeNode>();
TreeNode node = root;
while (node != null || !stack.isEmpty()) {
while (node != null) {
list.add(node);
stack.push(node);
node = node.left;
}
node = stack.pop();
node = node.right;
}
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;
}
}
}



从前序与中序遍历序列构造二叉树(中等)

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

提示:

  • 1 <= preorder.length <= 3000
  • inorder.length == preorder.length
  • -3000 <= preorder[i], inorder[i] <= 3000
  • preorder 和 inorder 均 无重复 元素
  • inorder 均出现在 preorder
  • preorder 保证 为二叉树的前序遍历序列
  • inorder 保证 为二叉树的中序遍历序列

示例 1:

12. 从前序与中序遍历序列构造二叉树 (中)示例

1
2
输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]

示例 2:

1
2
输入: preorder = [-1], inorder = [-1]
输出: [-1]

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
private Map<Integer, Integer> indexMap;

public TreeNode myBuildTree(int[] preorder, int[] inorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right) {
if (preorder_left > preorder_right) {
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;
}

public TreeNode buildTree(int[] preorder, int[] inorder) {
int n = preorder.length;
// 构造哈希映射,帮助我们快速定位根节点
indexMap = new HashMap<Integer, Integer>();
for (int i = 0; i < n; i++) {
indexMap.put(inorder[i], i);
}
return myBuildTree(preorder, inorder, 0, n - 1, 0, n - 1);
}
}

路径总和 III(中等)

给定一个二叉树的根节点 root ,和一个整数 targetSum ,求该二叉树里节点值之和等于 targetSum 的 路径 的数目。

路径 不需要从根节点开始,也不需要在叶子节点结束,但是路径方向必须是向下的(只能从父节点到子节点)。

提示:

  • 二叉树的节点个数的范围是 [0,1000]
  • -10^9 <= Node.val <= 10^9
  • -1000 <= targetSum <= 1000

示例 1:

13. 路径总和 III (中)示例

1
2
3
输入:root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
输出:3
解释:和等于 8 的路径有 3 条,如图所示。

示例 2:

1
2
输入:root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出:3

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
class Solution {
public int pathSum(TreeNode root, long targetSum) {
if (root == null) {
return 0;
}

int ret = rootSum(root, targetSum);
ret += pathSum(root.left, targetSum);
ret += pathSum(root.right, targetSum);
return ret;
}

public int rootSum(TreeNode root, long targetSum) {
int ret = 0;

if (root == null) {
return 0;
}
int val = root.val;
if (val == targetSum) {
ret++;
}

ret += rootSum(root.left, targetSum - val);
ret += rootSum(root.right, targetSum - val);
return ret;
}
}
/**
前缀和

**/
class Solution {
public int pathSum(TreeNode root, int targetSum) {
Map<Long, Integer> prefix = new HashMap<Long, Integer>();
prefix.put(0L, 1);
return dfs(root, prefix, 0, targetSum);
}

public int dfs(TreeNode root, Map<Long, Integer> prefix, long curr, int targetSum) {
if (root == null) {
return 0;
}

int ret = 0;
curr += root.val;

ret = prefix.getOrDefault(curr - targetSum, 0);
prefix.put(curr, prefix.getOrDefault(curr, 0) + 1);
ret += dfs(root.left, prefix, curr, targetSum);
ret += dfs(root.right, prefix, curr, targetSum);
prefix.put(curr, prefix.getOrDefault(curr, 0) - 1);

return ret;
}
}

二叉树的最近公共祖先(中等)

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

在有根树中,节点 p、q 的最近公共祖先,是同时作为两者祖先且深度最大的节点;一个节点也可以是它自己的祖先。

提示:

  • 树中节点数目在范围 [2, 10^5] 内。
  • -10^9 <= Node.val <= 10^9
  • 所有 Node.val 互不相同 。
  • p != q
  • p 和 q 均存在于给定的二叉树中。

示例 1:

14. 二叉树的最近公共祖先 (中)示例

1
2
3
输入:root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出:3
解释:节点 5 和节点 1 的最近公共祖先是节点 3 。

示例 2:

14. 二叉树的最近公共祖先 (中)示例

1
2
3
输入:root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出:5
解释:节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。

示例 3:

1
2
输入:root = [1,2], p = 1, q = 2
输出:1

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {

private TreeNode ans;

public Solution() {
this.ans = null;
}

private boolean dfs(TreeNode root, TreeNode p, TreeNode q) {
if (root == null) return false;
boolean lson = dfs(root.left, p, q);
boolean rson = dfs(root.right, p, q);
if ((lson && rson) || ((root.val == p.val || root.val == q.val) && (lson || rson))) {
ans = root;
}
return lson || rson || (root.val == p.val || root.val == q.val);
}

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
this.dfs(root, p, q);
return this.ans;
}
}

二叉树中的最大路径和(困难)

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

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

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

提示:

  • 树中节点数目范围是 [1, 3 * 10^4]
  • -1000 <= Node.val <= 1000

示例 1:

15. 二叉树中的最大路径和 (难)示例

1
2
3
输入:root = [1,2,3]
输出:6
解释:最优路径是 2 -> 1 -> 3 ,路径和为 2 + 1 + 3 = 6

示例 2:

15. 二叉树中的最大路径和 (难)示例

1
2
3
输入:root = [-10,9,20,null,null,15,7]
输出:42
解释:最优路径是 15 -> 20 -> 7 ,路径和为 15 + 20 + 7 = 42

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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 node.val + Math.max(leftGain, rightGain);
}
}

参考资料