day18 代码回想录 二叉树05 找树左下角的值&路径总和&从中序与后序遍历序列构造二叉树

大纲

● 513.找树左下角的值
● 112. 路径总和 113.路径总和ii
● 106.从中序与后序遍历序列构造二叉树 105.从前序与中序遍历序列构造二叉树

找树左下角的值

题目链接：513.找树左下角的值

// 寻找树最底层左边的值
// 中序遍历第一个值记录
// 层序遍历第一个值记录
int findBottomLeftValue(TreeNode* root)
{
    int ret = -1;
    if (!root) return -1;
    queue _queue;
    _queue.push(root);
    bool firstFlag = false; // 记录是否每层保存了第一个元素
    while(!_queue.empty()) {
        int size = _queue.size();
        firstFlag = false;
        for (int i = 0; i < size; ++i) {
            TreeNode* node = _queue.front();
            _queue.pop();
            if (!firstFlag) {
                ret = node->val;
                firstFlag = true;
            }
            if (node->left) _queue.push(node->left);
            if (node->right) _queue.push(node->right);
        }
    }
    return ret;
}
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

路径总和

题目链接：112. 路径总和

// 思路是利用递归
// 终止条件：叶子节点时 和 空节点时退出循环
// 参数：节点、路径和、目标值、是否满足叶子节点的路径和==目标值
// 循环体：节点的左右子节点计算总和
void calcSum(TreeNode* root, int pathSum, int target, bool& ret)
{
    if (!root) return;
    if (!root->left && !root->right) {
        if (pathSum + root->val == target)
            ret = true;
        return;
    }

    pathSum += root->val;
    calcSum(root->left, pathSum, target, ret);
    calcSum(root->right, pathSum, target, ret);
    pathSum -= root->val;
}

bool hasPathSum(TreeNode* root, int target)
{
    bool ret = false;
    int sum = 0;
    calcSum(root, sum, target, ret);
    return ret;
}

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

113.路径总和ii

题目链接：

// 路径总和2
void _getAllPath(TreeNode* root, vector& pathVec, int& pathSum, int target, vector>& ret)
{
    if (!root) return;
    // 叶子节点
    if (!root->left && !root->right) {
        if (pathSum + root->val == target) {
            vector tmp;
            for (int i = 0; i < pathVec.size(); ++i){
                tmp.push_back(pathVec[i]->val);
            }
            tmp.push_back(root->val);
            ret.push_back(tmp);
        }
        return;
    }
    pathVec.push_back(root);
    pathSum += root->val;
    _getAllPath(root->left, pathVec, pathSum, target, ret);
    _getAllPath(root->right, pathVec, pathSum, target, ret);
    pathSum -= root->val;
    pathVec.pop_back();
}

vector> getAllPath(TreeNode* root, int target)
{
    vector> ret;
    vector pathVec;
    int pathSum = 0;
    _getAllPath(root, pathVec, pathSum, target, ret);
    return ret;
}

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