Question
输入一颗二叉树的根节点和一个整数,打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中,数组长度大的数组靠前)
关键词:二叉树 求和 BFS
Solution
DFS
时间复杂度:O(log(N))
空间复杂度:O(N/2·log(N))
- Python
class Solution:
# 返回二维列表,内部每个列表表示找到的路径
def __init__(self):
self.ans = []
def FindPath(self, root, expectNumber):
if root:
self.dfs(root, expectNumber, [])
return self.ans
def dfs(self, node, num, path):
if not node.left and not node.right and node.val == num:
self.ans.append(path + [node.val])
if node.left:
self.dfs(node.left, num - node.val, path + [node.val])
if node.right:
self.dfs(node.right, num - node.val, path + [node.val])
- C++
class Solution {
public:
vector<vector<int> > FindPath(TreeNode* root,int expectNumber) {
vector<vector<int>> ans;
vector<int> temp;
if(root)
dfs(root, expectNumber, temp, ans);
return ans;
}
void dfs(TreeNode* node, int num, vector<int> &path, vector<vector<int>> &ans){
path.push_back(node->val);
if((node->left == NULL) && (node->right == NULL) && (node->val == num)){
//path.push_back(node->val);
ans.push_back(path);
}
if(node->left)
dfs(node->left, num - node->val, path, ans);
if(node->right)
dfs(node->right, num - node->val, path, ans);
path.pop_back();
}
};
版权声明:本文为weixin_44225792原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。