lc-day3

发表于

404. 左叶子之和

404. 左叶子之和

一个很简单的题目,我这里用dfs的遍历实现的，所以也就没有具体的遍历顺序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int ans = 0;
    int sumOfLeftLeaves(TreeNode* root) {
        dfs(root);
        return ans;
    }

    void dfs(TreeNode* root){
        if(root == nullptr) return;
        if(root->left) {
            if(root->left->left == nullptr && root->left->right == nullptr) 
                ans += root->left->val;
            dfs(root->left);
        }
        if(root->right) dfs(root->right);
    }
};

Carl的解法是标准的后序遍历方法，在了解了他的方法后我也仿写了一下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int sumOfLeftLeaves(TreeNode* root) {
        if(root == NULL) return 0;
        int left = sumOfLeftLeaves(root->left); //左
        int right = sumOfLeftLeaves(root->right);   //右
        //后序遍历法
        int sum = 0;
        if(root->left != NULL && root->left->left == NULL && root->left->right == NULL){
            sum = root->left->val;
        }//中
        return sum + left + right;
    }
};

时间复杂度O(n)，其中 n 是树中的节点个数。

空间复杂度O(n)，空间复杂度和深度优先搜索使用的栈内存有关，最坏情况下，树呈链式结构，深度为O(n),对应空间复杂度为O(n)

迭代法的实现

理论上来说能用递归的题目必然涉及到了栈， 那么就可以用迭代法模拟栈的运行写出题解，由于时间关系，这里就不说了，等下一轮复习的时候再刷一遍吧，我的想法是第一遍追求广度，第二遍后面追求深度！

513. 找树左下角的值

513. 找树左下角的值

拿到这个题第一反应是用bfs做，这种写法最简单，找到每一层第一个节点不断进行更新就可以了

bfs：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int findBottomLeftValue(TreeNode* root) {
        queue<TreeNode*> q;
        q.push(root);
        int ans = root->val;
        while(q.size()){
            int size = q.size();
            for(int i = 0; i < size; i++){
                TreeNode* temp = q.front();
                q.pop();
                if(i == 0) ans = temp->val;
                if(temp->left) q.push(temp->left);
                if(temp->right) q.push(temp->right);
            }
        }
        return ans;
    }
};

再贴一个我的dfs解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int maxH, ans;
    int findBottomLeftValue(TreeNode* root) {
        ans = root->val;
        dfs(root, 0);
        return ans;
    }
    void dfs(TreeNode* root, int depth){
        if(root == NULL) return ;
        if(maxH < depth) {
            ans = root->val;
            maxH = depth;
        }
        dfs(root->left, depth + 1);
        dfs(root->right, depth + 1);
    }
};

dfs的思路是不断地往左边找，每到最深一层就记录一下高度，最后就得到答案了

我感觉不是最优解，不太自信好像跟Carl的差不多，哈哈

112. 路径总和

路径综合

这个题目的测试点好恶心，故意卡边界，开局就两个边界给我干懵了。

对于根节点为空，直接返回false

对于根节点不为空，要特判整个树是否只有这一个节点并且等于target，返回true

处理完这两步后就可以写递归代码了，这题递归代码我采用了后序遍历，观察这个题你会发现，只要找出了一组答案，最终结果就是true了，这一点跟或（||）命令很像，只要有一个表达式为true满足了，整个表达式就为true。因此这里用后序遍历

在写完上面一段后，我突然发现有一个剪枝操作，如果有一个值为true，直接进入返回就好了

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
class Solution {
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
        if(root == NULL) return false;
            
        if(root->left == NULL && root->right == NULL && root->val == targetSum) 
            return true;
        return dfs(root->left, targetSum - root->val) || dfs(root->right, targetSum - root->val);
    }

    bool dfs(TreeNode* root, int targetSum){
        if(root == NULL) return false;
        if(root->left == NULL && root->right == NULL) {
            if(targetSum - root->val == 0) return true;
            else return false;
        }
        bool left = false, right = false;
        if(root->left) {
            left = dfs(root->left, targetSum - root->val);
            if(left) return true;	//剪枝，如果这一步执行了，后面的搜索就不用执行了
        }
        if(root->right) {
            right = dfs(root->right, targetSum - root->val);
            if(right) return true;	//后面的这个好像剪不掉了，为了整齐，还是加上吧
        }
        return left || right;
    }
};

剪枝

看了Carl的代码后感觉我太菜了，-_-，他的代码把边界情况处理的太好了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
        if(root == NULL) return false;

        return dfs(root, targetSum - root->val);
    }

    bool dfs(TreeNode* root, int targetSum){
        if(!root->left && !root->right && targetSum == 0) return true;
        if(!root->left && !root->right) return false;

        if(root->left) 
            if(dfs(root->left, targetSum - root->left->val)) return true;
        if(root->right)
            if(dfs(root->right, targetSum - root->right->val)) return true;
        return false;
    }
};

我在写这个题目时遇到了一个问题就是把握不住tar减去val的时机，把整个过程都弄乱了，虽然最后勉强过了。。。。。

感觉没啥收获

反思

Carl的解法是先在开头特判了根节点，然后后面的代码就统一化了，就有点像是打印“1->2->3->4”这个字符串一样，先打印出“1”，后面每一步打印“->num”，这是做pat的常用套路。他这里的代码就是tar减去root->left->val，然后留在在下一层判断

我的解法就很乱了，我是在每一个结点都减去当前结点的值，然后进入递归函数进行判断，这样势必导致最后写递归出口的时候还要再减一次if（targetSum - root->val == 0）… 这么写太啰嗦了

把突然想到很重要的一点补上， 什么时候需要返回值？

Carl的说法是如果要搜索整个树，那就不要返回值。如果只是需要返回某一条路径，就需要返回值，遇到了符合条件的路径就返回。有了这个结论，以后再写递归就不会眉毛胡子一把抓了。