Q1将有序数组转换为二叉搜索树
题目大致意思就是从一个数组建立平衡的二叉搜索树。由于数组以及进行了升序处理，我们只要考虑好怎么做到平衡的。平衡意味着左右子树的高度差不能大于1。由此我们可以想着是否能用类似二分+递归来解决。
-
如果left>right,直接返回nullpter
-
否则 mid = (left + right) / 2,将a[mid]值赋给root结点
-
递归左子树 right = mid-1;
-
递归右子树left = mid+1;
这样一来问题就得到了解决。
class Solution {
public:
TreeNode* sortedArrayToBST(vector<int>& nums) {
return build(nums,0,nums.size() - 1);
}
TreeNode*build(vector<int>&nums,int left,int right)
{
if(left > right)
return nullptr;
int mid = (left + right) / 2;
TreeNode*root = new TreeNode(nums[mid]);
root->left = build(nums,left,mid-1);
root->right = build(nums,mid+1,right);
return root;
}
};
Q2路径总和
本题是经典的搜索回溯+路径记录的题目。
路径记录:
-
先序进行递归遍历，进行路径更新
-
如果当前sum = root->val,将次路径添加到答案中
搜索回溯:
-
递推参数： 当前节点 root ，当前目标值 tar
-
终止条件： 若节点 root 为空，则直接返回。
-
递推工作：
-
路径更新： 将当前节点值 root.val 加入路径 path 。
-
目标值更新： tar = tar - root.val（即目标值 tar 从 targetSum 减至 0 ）
-
路径记录： 当 (1) root 为叶节点 且 (2) 路径和等于目标值 ，则将此路径 path 加入 res 。
-
先序遍历： 递归左 / 右子节点。
-
路径恢复： 向上回溯前，需要将当前节点从路径 path 中删除，即执行 path.pop_back() 。
class Solution {
public:
vector<vector<int>> ret;
vector<int> path;
void dfs(TreeNode*root,int targetSum)
{
if(root==nullptr)return;
path.push_back(root->val);
if(root->left == nullptr && root->right == nullptr)
{
if(targetSum == root->val)
ret.push_back(path);
}
dfs(root->left,targetSum-root->val);
dfs(root->right,targetSum-root->val);
path.pop_back();
}
vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
dfs(root,targetSum);
return ret;
}
};
本文由博客一文多发平台 OpenWrite 发布！