*算法训练（leetcode）第十四天 | 513. 找树左下角的值、112. 路径总和、106. 从中序与后序遍历序列构造二叉树、D

513. 找树左下角的值

leetcode题目地址

层序遍历，记录每一层的第一个结点，遍历结束后最后一次记录的就是左下角的值。（注意题目要求不是最左侧的节点，是最后一层的最左侧结点）

时间复杂度： $O(n)$
空间复杂度： $O(n)$

// c++
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int findBottomLeftValue(TreeNode* root) {
        // if(!root) return -1;
        queue<TreeNode*> qu;
        qu.push(root);
        int result;
        while(!qu.empty()){
            int size = qu.size();
            for(int i=0; i<size; i++){
                root = qu.front();                
                qu.pop();
                if(i==0) result = root->val;
                if(root->left) qu.push(root->left);
                if(root->right) qu.push(root->right);
            }
        }
        return result;
    }
};
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

112. 路径总和

leetcode题目地址

与之前做过的一道查找根节点到所有叶结点路径（leetcode 257题）的题目的思路是一致的，只不过是把结点加入路径改为节点值加入和。

时间复杂度： $O(n)$
空间复杂度： $O(n)$

// c++
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void Order(TreeNode* root, int sum, int target, bool &flag){
        if(!root || flag) return;

        sum += root->val;

        if(!root->left && !root->right && sum==target){
            flag = true;
            return;
        }
        if(!flag && root->left) Order(root->left, sum, target, flag);
        if(!flag && root->right) Order(root->right, sum, target, flag);
        
    }
    bool hasPathSum(TreeNode* root, int targetSum) {
        int sum = 0;
        bool flag = false;
        Order(root, sum, targetSum, flag);
        return flag;
    }
};
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

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

leetcode题目地址

本题属于一想就会，一写就废。代码实现起来相对复杂…
思路来源

时间复杂度： $O(n)$
空间复杂度： $O(n)$

// c++
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* createTree(vector<int>& inorder, 
                        vector<int>& postorder, 
                        int inleft, int inright,
                        int postleft, int postright){
        
        if(postleft > postright) return NULL;
        TreeNode* root = new TreeNode(postorder[postright]);
        if(postright-postleft == 0) return root;

        int splitIdx;
        for(splitIdx=0; splitIdx<=inright-inleft; splitIdx++)
            if(inorder[inleft+splitIdx] == postorder[postright]) break;
        
        root->left = createTree(inorder, postorder, inleft, inleft+splitIdx-1, postleft, postleft+splitIdx-1);
        root->right = createTree(inorder, postorder, inleft+splitIdx+1, inright, postleft+splitIdx, postright-1);
        return root;
    }
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        if(inorder.size() == 0) return NULL;
        TreeNode* root;
        // int size = inorder.size();
        root = createTree(inorder, postorder, 0, inorder.size()-1, 0, postorder.size()-1);
        return root;
    }
};
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
36
37
38
39