给你二叉树的根节点 root 和一个表示目标和的整数 targetSum ,判断该树中是否存在 根节点到叶子节点 的路径,这条路径上所有节点值相加等于目标和 targetSum 。
叶子节点 是指没有子节点的节点。
示例 1:
输入:root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出:true
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
bool haveTarget(TreeNode* node, int targetSum, int sum){
if (!node){
return false;
}
sum = sum+node->val;
if (!node->left&&!node->right){
if (targetSum == sum) return true;
else return false;
}
return haveTarget(node->left, targetSum, sum) || haveTarget(node->right, targetSum, sum);
}
bool hasPathSum(TreeNode* root, int targetSum) {
if (!root) return false;
return haveTarget(root, targetSum, 0);
}
};
给你二叉树的根节点 root 和一个整数目标和 targetSum ,找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
叶子节点 是指没有子节点的节点。
示例 1:
输入:root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出:[[5,4,11,2],[5,8,4,5]]
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<vector<int>> ans;
void findPath(TreeNode* node, int targetSum, int sum, vector<int>& tmp){
if (!node) return;
sum+=node->val;
tmp.push_back(node->val);
if (!node->left&&!node->right) {
if (sum == targetSum) ans.push_back(tmp);
tmp.pop_back();
return;
}
findPath(node->left, targetSum, sum, tmp);
findPath(node->right, targetSum, sum, tmp);
tmp.pop_back();
return;
}
vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
vector<int> tmp;
findPath(root, targetSum, 0, tmp);
return ans;
}
};
根据一棵树的中序遍历与后序遍历构造二叉树。
注意:
你可以假设树中没有重复的元素。
例如,给出
中序遍历 inorder = [9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]
返回如下的二叉树:
3
/ \
9 20
/ \
15 7
注意:这类题目一般用【下标标定左右子树的范围 】会比【创建左右子数组】好写一些。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* makeTree(vector<int>& inorder, vector<int>& postorder, int li, int ri, int lp, int rp){
if (li > ri) return nullptr;
int val = postorder[rp];
TreeNode* node = new TreeNode(val);
int interval = 0;
for (int i = li; i <= ri; ++i,++interval){
if (inorder[i] == val) break;
}
node->left = makeTree(inorder, postorder, li, li+interval-1, lp, lp+interval-1);
node->right = makeTree(inorder, postorder, li+interval+1, ri, lp+interval, rp-1);
return node;
}
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
TreeNode* root = makeTree(inorder, postorder, 0, inorder.size()-1, 0, postorder.size()-1);
return root;
}
};
给定一个不含重复元素的整数数组 nums 。一个以此数组直接递归构建的 最大二叉树 定义如下:
二叉树的根是数组 nums 中的最大元素。
左子树是通过数组中 最大值左边部分 递归构造出的最大二叉树。
右子树是通过数组中 最大值右边部分 递归构造出的最大二叉树。
返回有给定数组 nums 构建的 最大二叉树 。
示例 1:
输入:nums = [3,2,1,6,0,5]
输出:[6,3,5,null,2,0,null,null,1]
解释:递归调用如下所示:
- [3,2,1,6,0,5] 中的最大值是 6 ,左边部分是 [3,2,1] ,右边部分是 [0,5] 。
- [3,2,1] 中的最大值是 3 ,左边部分是 [] ,右边部分是 [2,1] 。
- 空数组,无子节点。
- [2,1] 中的最大值是 2 ,左边部分是 [] ,右边部分是 [1] 。
- 空数组,无子节点。
- 只有一个元素,所以子节点是一个值为 1 的节点。
- [0,5] 中的最大值是 5 ,左边部分是 [0] ,右边部分是 [] 。
- 只有一个元素,所以子节点是一个值为 0 的节点。
- 空数组,无子节点。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
void getmax(vector<int>& nums, int left, int right, int& max, int& index){
max = nums[left]; index = left;
for (int i = left+1; i <= right; ++i){
if (nums[i] > max){
max = nums[i];
index = i;
}
}
}
TreeNode* makeTree(vector<int>& nums, int left, int right){
if (left > right) return nullptr;
int maxval = 0, index = -1;
getmax(nums, left, right, maxval, index);
TreeNode* node = new TreeNode(maxval);
node->left = makeTree(nums, left, index-1);
node->right = makeTree(nums, index+1, right);
return node;
}
TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
TreeNode* root = makeTree(nums, 0, nums.size()-1);
return root;
}
};