代码随想录算法训练营第十七天-二叉树-654.最大二叉树

• 凡是构造二叉树类题目，都要用前序遍历
• 再次强调，完成二叉树的问题，主要就是遍历顺序密切相关，但也不绝对，应该是第一要务

// d17-leetcode-binarytree-constructmaximumbinarytree.cpp
#include <iostream>
#include <vector>
#include <sstream>
#include <climits>

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(): val(0), left(nullptr), right(nullptr) {}
    TreeNode(int v): val(v), left(nullptr), right(nullptr) {}
    TreeNode(int v, TreeNode* l, TreeNode* r): val(v), left(l), right(r) {}
};

class Solution {
private:
    TreeNode* traversal(std::vector<int>& nums, int left, int right) {
        if (left >= right)
            return nullptr;
        int maxIndex = left;
        for (int i = left + 1; i < right; ++i) {
            if (nums.at(i) > nums.at(maxIndex))
                maxIndex = i;
        }
        TreeNode* node = new TreeNode(nums.at(maxIndex));
        node->left = traversal(nums, left, maxIndex);
        node->right = traversal(nums, maxIndex + 1, right);
        return node;
    }
public:
    TreeNode* constructMaximumBinaryTree(std::vector<int>& nums) {
        return traversal(nums, 0, nums.size());
    }
};

std::vector<int> vec;
void getNums() {
    std::string str;
    getline(std::cin, str);
    std::stringstream ss {str};
    int v;
    while(ss >> v)
        vec.push_back(v);
}
void showTree(TreeNode* node) {
    if (node == nullptr)
        return;
    std::cout << node->val << " ";
    showTree(node->left);
    showTree(node->right);
}

int main()
{
    getNums();
    Solution s;
    TreeNode* ptn = s.constructMaximumBinaryTree(vec);
    showTree(ptn);
    std::cout << std::endl;

    return 0;
}

• 汇总