代码随想录 | Day20 | 二叉树：二叉树所有路径&&左叶子之和

主要学习内容：

1.利用二叉树的谦虚遍历进行题目解答

2.to_string函数的使用

257.二叉树所有路径

257. 二叉树的所有路径 - 力扣（LeetCode）

解法一：直接遍历

本次使用的是前序遍历

1.函数参数和返回值

1
void tra(string s,TreeNode *t)

如果不使用全局变量vector的话为

1
void tra(vector<string>,string s,TreeNode *t)

2.终止条件

1
2
3
4
5
6
7
8
if(t==nullptr)
	return;
if(t->left==nullptr&&t->right==nullptr)
{
	s+=to_string(t->val);
	res.push_back(s);
	return;
}

只有我们遍历到叶子结点的时候才能收集结果，而前面的非空判断是确保有左右孩子

然后正常收集结果，注意to_string函数的使用

3.本层代码逻辑

1
2
3
4
s+=to_string(t->val);
s+="->";
tra(s,t->left);
tra(s,t->right);

如果不是叶子结点就会进入本层代码逻辑，加入”->”和t->val，然后继续遍历左右子树

4.完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    vector<string> res;
    void tra(string s,TreeNode *t)
    {
        if(t==nullptr)
            return;
        if(t->left==nullptr&&t->right==nullptr)
        {
            s+=to_string(t->val);
            res.push_back(s);
            return;
        }
        s+=to_string(t->val);
        s+="->";
        tra(s,t->left);
        tra(s,t->right);
    }
    vector<string> binaryTreePaths(TreeNode* root) {
        string s;
        tra(s,root);
        return res;
    }
};

解法二：回溯法

就是经典的回溯算法求路径+把路径处理为字符串，可以等到学完回溯算法后再回来掌握。

这里附上代码随想录的解答

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
30
31
32
33
34
35
class Solution {
private:

    void traversal(TreeNode* cur, vector<int>& path, vector<string>& result) {
        path.push_back(cur->val); // 中，中为什么写在这里，因为最后一个节点也要加入到path中 
        // 这才到了叶子节点
        if (cur->left == NULL && cur->right == NULL) {
            string sPath;
            for (int i = 0; i < path.size() - 1; i++) {
                sPath += to_string(path[i]);
                sPath += "->";
            }
            sPath += to_string(path[path.size() - 1]);
            result.push_back(sPath);
            return;
        }
        if (cur->left) { // 左 
            traversal(cur->left, path, result);
            path.pop_back(); // 回溯
        }
        if (cur->right) { // 右
            traversal(cur->right, path, result);
            path.pop_back(); // 回溯
        }
    }

public:
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> result;
        vector<int> path;
        if (root == NULL) return result;
        traversal(root, path, result);
        return result;
    }
};

404.左叶子之和

404. 左叶子之和 - 力扣（LeetCode）

代码随想录的后序遍历很容易把人绕晕，建议用前序遍历直接做

解法：前序遍历

就把他当做一个普通的遍历+两个if判断即可

1.函数参数和返回值

1
void tra(TreeNode *t)

如果不使用全局变量vector的话为，sum为当前的叶子之和

1
void tra(TreeNode *t,int sum)

2.终止条件

1
2
if(t==nullptr)
            return;

3.本层代码逻辑

1
2
3
4
5
if(t->left!=nullptr)
 	if(t->left->left==nullptr&&t->left->right==nullptr)
		sum+=t->left->val;
tra(t->left);
tra(t->right);

判断左子树是否为空，不为空判断是不是左叶子，如果是的话就加上，不是的话就继续遍历即可

完整代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int sum=0;
    void tra(TreeNode *t)
    {
        if(t==nullptr)
            return;
        if(t->left!=nullptr)
            if(t->left->left==nullptr&&t->left->right==nullptr)
                sum+=t->left->val;
        tra(t->left);
        tra(t->right);
    }
    int sumOfLeftLeaves(TreeNode* root) {
        tra(root);
        return sum;
    }
};