有关树的搜索问题一般都可以通过递归写出来。
一.
题目:Path Sum
Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.
For example:
Given the below binary tree and sum = 22,
5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1
return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.
解题思想
题目意思是给了一个二叉树，每个节点对应一个值，同时给了一个指定的树。 然后请问是否有一条从根节点开始，到叶节点的路径，其和正好等于那个值。
做法就是简单的DFS，如果到了叶节点刚好等于那个值就返回True，如果不够或者超过则返回False（搜索的时候如果还没到叶节点就超了，就回溯回去）。
代码：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public:
void dfs(TreeNode* root, int sum, bool& ret){
if(sum == root -> val && !root -> left && !root -> right){
ret = true;
return;
}
if(!root-> left && !root -> right)
return;
if(root -> left)
dfs(root -> left, sum - root -> val, ret);
if(root -> right)
dfs(root -> right, sum - root -> val, ret);
}
bool hasPathSum(TreeNode* root, int sum) {
bool ret = false;
if(root == NULL)
return ret;
dfs(root, sum, ret);
return ret;
}
或者代码：
public class Solution {
bool hasPathSum(TreeNode *root, int sum) {
if (root == NULL) return false;
if (root->val == sum && root->left == NULL && root->right == NULL) return true;
return hasPathSum(root->left, sum-root->val) || hasPathSum(root->right, sum-root->val);
}
}
变形1.Leetcode 113. Path Sum II 路径和2
Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.
For example:
Given the below binary tree and sum = 22,
5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1
return
[
[5,4,11,2],
[5,8,4,5]
]
解题思想和上题类似，只不过上题是判读是否存在这样的路径，而该题是找出这样的路径.
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
/**
* 和原来的不一样，这题要完全遍历，使用track跟踪当前的进度，进入dfs时压进去，出dfs时推出，当时叶节点且和正好为0是，克隆添加到结果中。
* */
public class Solution {
List<List<Integer>> list;
LinkedList<Integer> track;
public void dfs(TreeNode root,int sum){
if(root==null)
return;
sum-=root.val;
track.add(root.val);
if(sum==0 && root.left==null && root.right==null)
list.add((LinkedList<Integer>)track.clone());
dfs(root.left,sum);
dfs(root.right,sum);
track.remove(track.size()-1);
}
public List<List<Integer>> pathSum(TreeNode root, int sum) {
this.list=new ArrayList<List<Integer>>();
this.track=new LinkedList<Integer>();
dfs(root,sum);
return this.list;
}
}
变形3.Path Sum III
You are given a binary tree in which each node contains an integer value.
Find the number of paths that sum to a given value.
The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).
The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000.
例子.
root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8
10
/ \
5 -3
/ \ \
3 2 11
/ \ \
3 -2 1
Return 3. The paths that sum to 8 are:
1. 5 -> 3
2. 5 -> 2 -> 1
3. -3 -> 11
代码：
/**
* 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 pathSum(TreeNode* root, int sum) {
if(root == NULL)
return 0;
return dfs(root, sum) + pathSum(root -> left, sum) + pathSum(root -> right, sum);
}
int dfs(TreeNode* root, int sum){
int ret = 0;
if(root == NULL)
return ret;
if(sum == root -> val)
ret ++;
ret += dfs(root -> left, sum - root -> val);
ret += dfs(root -> right, sum - root -> val);
return ret;
}
};
下面两道也是很相似的两道，都需要找到从根到每个叶子节点的所有路径。
前者是打印出每一个从根到叶子节点的路径，后一个是求出所有路径中的最小深度，在求解第二个问题的时候，我先是按照第一道题的思路，求出根到叶子节点的所有路径，然后再从中找出最小深度的。
问题一.Binary Tree Paths
Given a binary tree, return all root-to-leaf paths.
For example, given the following binary tree:
1
/ \
2 3
\
5
All root-to-leaf paths are:
["1->2->5", "1->3"]
代码：
/**
* 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:
void binaryTreePath(vector<string>& result, TreeNode* root, string t) {
if(!root->left && !root->right) {
result.push_back(t);
return;
}
if(root->left) binaryTreePath(result, root->left, t + "->" + to_string(root->left->val));
if(root->right) binaryTreePath(result, root->right, t + "->" + to_string(root->right->val));
}
vector<string> binaryTreePaths(TreeNode* root) {
vector<string> result;
if(!root) return result;
binaryTreePath(result, root, to_string(root->val));
return result;
}
};
问题二.Minimum Depth of Binary Tree
Given a binary tree, find its minimum depth.
The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.
解题思路：先按照上面问题的思路得到所有根到叶子节点的深度，放在一个vector中，然后遍历整个vector,找到最小的路径深度,本来以为整个过程下来会超时，没想到AC了。
代码:
/**
* 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:
void dfs(vector<int>& allDepth, TreeNode* root, int depth){
if(root -> left == NULL && root -> right == NULL){
allDepth.push_back(depth);
return;
}
if(root->left) dfs(allDepth, root->left, depth + 1);
if(root->right) dfs(allDepth, root->right, depth + 1);
}
int minDepth(TreeNode* root) {
if(root == NULL)
return 0;
vector<int> allDepth;
int depth = 1;
dfs(allDepth, root, depth);
int min = allDepth[0];
for(int i = 1; i < allDepth.size(); i ++){
if(allDepth[i] < min)
min = allDepth[i];
}
return min;
}
};
