lc-day4

发表于

113. 路径总和 II

题目

经过昨天的思考后，今天这题能直接秒了。仔细观察这个写法，我发现递归函数dfs每次都对函数进行了判断，判断这个

点是不是叶子节点，所以这对所有节点适用，但要记得此时的tar已经减去了这层的节点值了

关于特判，这个题只有主函数特判了初始的节点，后面如果再出现空节点函数dfs会忽略过去

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    vector<vector<int>> result;
    vector<int> path;
    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        if(root == NULL) return result;
        path.push_back(root->val);
        dfs(root, targetSum - root->val);
        return result;
    }

    void dfs(TreeNode* root, int targetSum){
        if(root->left == NULL && root->right == NULL && targetSum == 0) {
            result.push_back(path);
            return ;
        }
        if(root->left){
            path.push_back(root->left->val);
            dfs(root->left, targetSum - root->left->val);
            path.pop_back();
        }
        if(root->right){
            path.push_back(root->right->val);
            dfs(root->right, targetSum - root->right->val);
            path.pop_back();

        }
    }
};

通过

106. 从中序与后序遍历序列构造二叉树

题目

这个已经一两个月没写了，忘完了，直接看题解吧 ^_^

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    unordered_map<int, int> p;
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        int n = inorder.size();
        for(int i = 0; i < n; i++){
            p[inorder[i]] = i;
        }
        return dfs(inorder, postorder, 0, n - 1, 0, n - 1);
    }

    TreeNode* dfs(vector<int>& inorder, vector<int>& postorder, int il, int ir, int pl, int pr){
        if(pl > pr) return NULL;
        int key = postorder[pr];
        int k = p[key] - il;
        TreeNode* root = new TreeNode(key);
        root->left = dfs(inorder, postorder, il, il + k - 1, pl, pl + k - 1);
        root->right = dfs(inorder, postorder, il + k + 1, ir, pl + k, pr - 1);
        return root;
    }
};

用的y总的模板

难点1：边界处理，这里的边界是左闭右闭

难点2：后续遍历，在经过前几日的后序遍历的洗礼后，现在看后序遍历就有更新的体会了，这题用后序遍历特别巧妙的把一个问题划分为若干个子问题解决

再研究一下Carl的解法

我选择死亡，太多了。。。。。

不写啦

105. 从前序与中序遍历序列构造二叉树

题目

直接套用上一题的模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    unordered_map<int, int> pos;
    TreeNode* buildTree(vector<int>& pre, vector<int>& in) {
        int n = pre.size();
        for(int i = 0; i < n; i++) pos[in[i]] = i;
        return dfs(pre, in, 0, n - 1, 0, n - 1);
    }

    TreeNode* dfs(vector<int>& pre, vector<int>& in, int pl, int pr, int il, int ir){
        if(pl > pr) return NULL;
        int key = pre[pl];
        int k = pos[key] - il;
        TreeNode* root = new TreeNode(key);
        root->left = dfs(pre, in, pl + 1, pl + 1 + k - 1, il, il + k - 1);
        root->right = dfs(pre, in, pl + k + 1, pr, il + k + 1, ir);
        return root;
    }
};

五分钟搞定！