二叉树构建与遍历-LeetCode 889、1008、129、113

算法工程师之路

发布于 2019-11-26 06:08:46

55500

代码可运行

文章被收录于专栏：算法工程师之路算法工程师之路

运行总次数：0

代码可运行

编程题

【LeetCode #889】根据前序和后序遍历构建二叉树

返回与给定的前序和后序遍历匹配的任何二叉树。 pre 和 post 遍历中的值是不同的正整数。

示例：输入：pre = [1,2,4,5,3,6,7], post = [4,5,2,6,7,3,1] 输出：[1,2,3,4,5,6,7]

解题思路：

还是一样的套路，找出左右子树的数值范围，然后递归的构建！我们知道pre中第一个值为根节点的值，而post最后一个是根节点的值！并且这两个遍历的方式区别为： pre: 根节点前序左节点前序右节点 post: 后序左节点后序有节点根节点因此，第一次构建左子树时，将根节点去除，则此时子树根节点为2，那么就可以由post得到该子树的长度，进而将pre和post拆分成两个序列！转化为构建左右子树的子问题！

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* constructFromPrePost(vector<int>& pre, vector<int>& post) {
        if(pre.size() == 0 || post.size() == 0)  return nullptr;
        TreeNode* root = new TreeNode(pre[0]);
        if(pre.size() == 1) return root;   // 由于下面要使用pre[1]，因此必须判断其个数
        auto it = find(post.begin(), post.end(), pre[1]);
        int len = it - post.begin() + 1;   // 左子树长度
        vector<int> preleft(pre.begin()+1, pre.begin()+1+len);   // 一样的套路，不在赘述
        vector<int> preright(pre.begin()+1+len, pre.end());
        vector<int> postleft(post.begin(), post.begin()+len);
        vector<int> postright(post.begin()+len, post.end()-1);

        root->left = constructFromPrePost(preleft, postleft);
        root->right = constructFromPrePost(preright, postright);
        return root;
    }
};

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-postorder-traversal/

【LeetCode #1008】先序遍历构造二叉树

返回与给定先序遍历 preorder 相匹配的二叉搜索树（binary search tree）的根结点。

(回想一下，二叉搜索树是二叉树的一种，其每个节点都满足以下规则，对于 node.left 的任何后代，值总 < node.val，而 node.right 的任何后代，值总 > node.val。此外，先序遍历首先显示节点的值，然后遍历 node.left，接着遍历 node.right。）

示例：输入：[8,5,1,7,10,12] 输出：[8,5,10,1,7,null,12]

解题思路：

与使用前中序，中后序构建二叉树类似，这里要构建的是二叉搜索树，其有一个特点就是，根节点的值大于左子节点的值，而小于右子节点的值，因此我们可以根据这个性质，将preorder分开，已知根节点为preorder[0]，则其左子树一定都小于这个值，并且均为连续的序列！因此我们可以使用lower_bound去查找刚好大于等于preorder[0]的值，将整个序列分开，从而变成两个子问题分别构建左子树和右子树！

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* bstFromPreorder(vector<int>& preorder) {
        if(preorder.size() == 0)  return nullptr;
        TreeNode* root = new TreeNode(preorder[0]);
        auto it = lower_bound(preorder.begin()+1, preorder.end(), preorder[0]);
        vector<int> preleft(preorder.begin()+1, it);
        vector<int> preright(it, preorder.end());
        root->left = bstFromPreorder(preleft);
        root->right = bstFromPreorder(preright);
        return root;
    }
};

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/construct-binary-search-tree-from-preorder-traversal

【LeetCode #129】求根到叶子节点数字之和

给定一个二叉树，它的每个结点都存放一个 0-9 的数字，每条从根到叶子节点的路径都代表一个数字。例如，从根到叶子节点路径 1->2->3 代表数字 123。计算从根到叶子节点生成的所有数字之和。说明: 叶子节点是指没有子节点的节点。

示例 1: 输入: [1,2,3] 1 / \ 2 3 输出: 25 解释: 从根到叶子节点路径 1->2 代表数字 12. 从根到叶子节点路径 1->3 代表数字 13. 因此，数字总和 = 12 + 13 = 25.

解题思路：

使用dfs算法，递归的遍历每条路径，这个算法虽然有点复杂，但可以很轻松的拓展到其他问题！至于如何拓展，请看下题~

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> res;
    void dfs(TreeNode* root, int tmp){
        tmp += root->val;
        if(root->left == nullptr && root->right == nullptr){
            res.push_back(tmp);
            return;
        }
        if(root->left != nullptr)
            dfs(root->left, tmp*10);
        if(root->right != nullptr)
            dfs(root->right, tmp*10);
    }
    int sumNumbers(TreeNode* root) {
        if(root == nullptr)  return 0;
        int sum = 0;
        dfs(root, 0);
        for(auto i: res){
            sum += i;
        }
        return sum;
    }
};

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/sum-root-to-leaf-number

【LeetCode #113】路径总和 II

解题思路：

与上面题目的递归形式是一样的，区别时，我们在判断和的值之后要把遍历的节点进行保存！

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> res; 
    vector<int> tmp;
    void dfs(TreeNode* root, int sum){
        tmp.push_back(root->val);
        if(root->left == nullptr && root->right == nullptr && sum == root->val){
            res.push_back(tmp);
            return;
        }
        if(root->left != nullptr){

            dfs(root->left,  sum-root->val);
            tmp.pop_back();
        }
        if(root->right != nullptr){

            dfs(root->right,  sum-root->val);
            tmp.pop_back();
        }
    }

    vector<vector<int>> pathSum(TreeNode* root, int sum) {
        if(root == nullptr) return res;
        dfs(root, sum);
        return res;
    }
};