LeetCode二叉树小题目

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 发布！