跳转至

Day16 | Part6

约 66 个字 49 行代码 预计阅读时间 1 分钟

654.最大二叉树

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
TreeNode* build(vector<int>& nums, int l, int r) {
    if(l > r) return nullptr;
    int max_idx = l;
    for (int i = l; i <= r;i ++) 
        if(nums[i] > nums[max_idx]) max_idx = i;
    auto root = new TreeNode(nums[max_idx]);
    root->left = build(nums, l, max_idx - 1);
    root->right = build(nums, max_idx + 1, r);
    return root;
}
TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
    return build(nums, 0, nums.size() - 1);
}

617.合并二叉树

1
2
3
4
5
6
7
8
9
TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
    if(!root1) return root2;
    if(!root2) return root1;
    TreeNode* root = new TreeNode(0); // 定义新节点
    root->val = root1->val + root2->val;
    root->left = mergeTrees(root1->left, root2->left);
    root->right = mergeTrees(root1->right, root2->right);
    return root;
}

700.二叉搜索树中的搜索

二叉搜索树: 若左不空,则左都小于根,若右不空,则右都大于根

递归: 

1
2
3
4
5
6
TreeNode* searchBST(TreeNode* root, int val) {
    if(!root || root->val == val) return root;
    if(root->val > val) return searchBST(root->left, val);
    if(root->val < val) return searchBST(root->right, val);
    return nullptr;
}

迭代: 

1
2
3
4
5
6
7
8
TreeNode* searchBST(TreeNode* root, int val) {
    while(root) {
        if(root->val > val) root = root->left;
        else if(root->val < val) root = root->right;
        else return root;
    }
    return nullptr;
}

98.验证二叉搜索树

看中序遍历是否有序即可 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
void dfs(TreeNode* root, vector<int>& vec) {
    if(!root) return;
    dfs(root->left, vec);
    vec.push_back(root->val); // 转为数组
    dfs(root->right, vec);
}
bool isValidBST(TreeNode* root) {
    vector<int> vec;
    dfs(root, vec); // 中序转为数组,看有序否
    for(int i = 1; i < vec.size(); i ++)
        if(vec[i] <= vec[i - 1]) return false;
    return true;
}

颜色主题调整

快来和我聊天~

可以的话请给我赞和 star喔~    =>  GitHub stars

评论