这篇文章主要讲得是leetcode中的树的题目，主要解法都是dfs。
路径总和
给定一棵二叉树和一个总和，确定该树中是否存在根到叶的路径，这条路径的所有值相加等于给定的总和。
例如： 给定下面的二叉树和
总和 = 22，1
2
3
4
5
6
75
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1返回
true, 因为存在总和为 22 的根到叶的路径5->4->11->2。C++:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool hasPathSum(TreeNode* root, int sum) {
if(!root) return false;
if(!root->left && !root->right && sum == root->val) return true;
return hasPathSum(root->left, sum - root->val) || hasPathSum(root->right, sum - root->val);
}
};Python:
1
2
3
4
5
6
7
8
9
10
11
12# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def hasPathSum(self, root, sum):
if not root: return False
if not root.left and not root.right and root.val == sum: return True
return self.hasPathSum(root.left, sum - root.val) or self.hasPathSum(root.right, sum - root.val)
路径总和 II
给定一个二叉树和一个和，找到所有从根到叶路径总和等于给定总和的路径。
例如， 给定下面的二叉树和
sum = 22,1
2
3
4
5
6
75
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1返回
1
2
3
4[
[5,4,11,2],
[5,8,4,5]
]C++:
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/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
private:
vector<vector<int>> res;
public:
void dfs(TreeNode* root, int sum, vector<int>& tmp) {
if(!root)
return;
tmp.push_back(root->val);
if(!root->left && !root->right && sum == root->val)
res.push_back(tmp);
dfs(root->left, sum - root->val, tmp);
dfs(root->right, sum - root->val, tmp);
tmp.pop_back();
}
vector<vector<int>> pathSum(TreeNode* root, int sum) {
if(!root) return res;
vector<int> tmp;
dfs(root, sum, tmp);
return res;
}
};Python:
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# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def pathSum(self, root, sum):
"""
:type root: TreeNode
:type sum: int
:rtype: List[List[int]]
"""
res = []
path = []
def dfs(root, sum, path):
path.append(root.val)
if not root.left and not root.right and root.val == sum: res.append(path[:])
if root.left : dfs(root.left, sum - root.val, path)
if root.right : dfs(root.right, sum - root.val, path)
path.pop()
if not root : return []
dfs(root, sum, path)
return res
路径总和 III
给定一个二叉树，二叉树的每个节点含有一个整数。
找出路径和等于给定数的路径总数。
路径不需要从根节点开始，也不需要在叶节点结束，当路径方向必须是向下的（只从父节点到子节点）。
二叉树不超过1000个节点，节点的整数值的范围是[-1000000,1000000]。
示例：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8
10
/ \
5 -3
/ \ \
3 2 11
/ \ \
3 -2 1
返回 3. 和等于8的路径有:
1. 5 -> 3
2. 5 -> 2 -> 1
3. -3 -> 11C++:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int dfs(TreeNode* root, int sum) {
if(!root)
return 0;
return (sum == root->val) + dfs(root->left, sum - root->val) + dfs(root->right, sum - root->val);
}
int pathSum(TreeNode* root, int sum) {
if(!root) return 0;
return dfs(root, sum) + pathSum(root->left, sum) + pathSum(root->right, sum);
}
};Python:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def pathSum(self, root, sum):
"""
:type root: TreeNode
:type sum: int
:rtype: int
"""
if not root: return 0
return self.helper(root, sum) + self.pathSum(root.left, sum) + self.pathSum(root.right, sum)
def helper(self, root, sum):
if not root: return 0
return (1 if root.val == sum else 0) + \
self.helper(root.left, sum - root.val) + \
self.helper(root.right, sum - root.val)
二叉树的最近公共祖先
给定一棵二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义： “对于有根树T的两个结点u、v，最近公共祖先表示一个结点x，满足x是u、v的祖先且x的深度尽可能大。”（一个节点也可以是它自己的祖先）
1
2
3
4
5
6
7_______3______
/ \
___5__ ___1__
/ \ / \
6 _2 0 8
/ \
7 4例如，节点
5和节点1的最近公共祖先是节点3；节点5和节点4的最近公共祖先是节点5，因为根据定义，一个节点可以是它自己的祖先。后序遍历
C++:
1
2
3
4
5
6
7
8
9
10
11
12class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(!root || root == p || root == q)
return root;
TreeNode* left = lowestCommonAncestor(root->left, p, q);
TreeNode* right = lowestCommonAncestor(root->right, p, q);
if(left && right)
return root;
return left != NULL? left : right;
}
};Python:
1
2
3
4
5
6
7
8
9
10
11
12class Solution(object):
def lowestCommonAncestor(self, root, p, q):
"""
:type root: TreeNode
:type p: TreeNode
:type q: TreeNode
:rtype: TreeNode
"""
if not root or p == root or q == root: return root
left = self.lowestCommonAncestor(root.left, p, q)
right = self.lowestCommonAncestor(root.right, p, q)
return root if left and right else left or right
求根叶数字总和
给定一个只包含
0-9数字的二叉树，每个根到叶的路径可以代表一个数字。例如，从根到叶路径
1->2->3则代表数字123。查找所有根到叶数字的总和。
例如，
1
2
31
/ \
2 3根到叶子路径
1->2表示数字12。 根到叶子路径1->3表示数字13。返回总和 = 12 + 13 =
25。C++:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20class Solution {
private:
int res = 0;
public:
void dfs(TreeNode* root, int num){
if(!root) return;
if(!root->left && !root->right){
res += num * 10 + root->val;
return;
}
dfs(root->left, num * 10 + root->val);
dfs(root->right, num * 10 + root->val);
}
int sumNumbers(TreeNode* root) {
if(!root) return 0;
dfs(root, 0);
return res;
}
};Python:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17class Solution(object):
sum = 0
def sumNumbers(self, root):
"""
:type root: TreeNode
:rtype: int
"""
def dfs(root, path):
path.append(root.val)
if not root.left and not root.right: self.sum += int(''.join(str(i) for i in path))
if root.left: dfs(root.left, path)
if root.right: dfs(root.right, path)
path.pop()
if not root: return 0
dfs(root, [])
return self.sum二叉树中的最大路径和
给出一棵二叉树，寻找一条路径使其路径和最大。
对于这个问题，路径被定义为从树中任意节点连接任意节点的序列。该路径必须至少包含一个节点，并且不需要经过根节点。
例如：
给出一棵二叉树：
1
2
31
/ \
2 3返回
6。C++:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18class Solution {
private:
int res = -0x80000000;
public:
int dfs(TreeNode* root){
if(!root) return 0;
int left = max(0, dfs(root->left));
int right = max(0, dfs(root->right));
res = max(res, left + right + root->val);
return max(left, right) + root->val;
}
int maxPathSum(TreeNode* root) {
if(!root) return 0;
dfs(root);
return res;
}
};Python:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16class Solution(object):
s = -0x80000000
def maxPathSum(self, root):
"""
:type root: TreeNode
:rtype: int
"""
def dfs(node):
if not node: return 0
left = max(0, dfs(node.left))
right = max(0, dfs(node.right))
self.s = max(self.s, left + right + node.val)
return max(left, right) + node.val
dfs(root)
return self.s
