有關(guān)樹的搜索問題一般都可以通過遞歸寫出來。
一.
題目: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.
解題思想
題目意思是給了一個二叉樹，每個節(jié)點對應(yīng)一個值，同時給了一個指定的樹。 然后請問是否有一條從根節(jié)點開始，到葉節(jié)點的路徑，其和正好等于那個值。
做法就是簡單的DFS，如果到了葉節(jié)點剛好等于那個值就返回True，如果不夠或者超過則返回False（搜索的時候如果還沒到葉節(jié)點就超了，就回溯回去）。
代碼：
/**
* 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跟蹤當(dāng)前的進度，進入dfs時壓進去，出dfs時推出，當(dāng)時葉節(jié)點且和正好為0是，克隆添加到結(jié)果中。
* */
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;
}
};
下面兩道也是很相似的兩道，都需要找到從根到每個葉子節(jié)點的所有路徑。
前者是打印出每一個從根到葉子節(jié)點的路徑，后一個是求出所有路徑中的最小深度，在求解第二個問題的時候，我先是按照第一道題的思路，求出根到葉子節(jié)點的所有路徑，然后再從中找出最小深度的。
問題一.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.
解題思路：先按照上面問題的思路得到所有根到葉子節(jié)點的深度，放在一個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;
}
};
