构建二叉搜索树ii

unique-binary-search-trees-ii

http://www.nowcoder.com/questionTerminal/98aaaefacaca44b9b4f2f2bd75780664

后序遍历的变体,先将左右子树的所有搭配方式到两个vector,然后再用根节点分别与左右子树搭配:

//
// Created by jt on 2020/8/23.
//
#include <vector>
using namespace std;


class Solution {
public:
    /**
     *
     * @param n int整型
     * @return TreeNode类vector
     */
    vector<TreeNode *> generateTrees(int n) {
        // write code here
        return postOrder(1, n);
    }

    vector<TreeNode *> postOrder(int left, int right) {
        vector<TreeNode *> res;
        if (left > right) return vector<TreeNode *>{nullptr};
        for (int i = left; i <= right; ++i) {
            vector<TreeNode *> leftVec = postOrder(left, i-1);
            vector<TreeNode *> rightVec = postOrder(i+1, right);
            for (int j = 0; j < leftVec.size(); j++) {
                for (int k = 0; k < rightVec.size(); k++) {
                    // 根节点建立必须在循环内部
                    TreeNode *root = new TreeNode(i);
                    root->left = leftVec[j];
                    root->right = rightVec[k];
                    res.push_back(root);
                }
            }
        }
        return res;
    }
};
刷遍天下无敌手 文章被收录于专栏

秋招刷题历程

全部评论

相关推荐

头像
02-26 13:58
门头沟学院 Java
北城_阿亮:把八股背一背,包装一下实习经历项目经历,要是有心思考证就考一考,然后把别人的项目爬到自己github上,包装到简历里,什么三个月?一个月!
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务