【leetcode刷题】T148-修剪二叉搜索树

木又AI帮

发布于 2019-08-28 15:11:46

4020

发布于 2019-08-28 15:11:46

文章被收录于专栏：木又AI帮

木又连续日更第8天（8/138）

木又的第148篇leetcode解题报告

二叉树类型第38篇解题报告

leetcode第669题：修剪二叉搜索树

https://leetcode-cn.com/problems/trim-a-binary-search-tree/

【题目】

给定一个二叉搜索树，同时给定最小边界L 和最大边界 R。通过修剪二叉搜索树，使得所有节点的值在[L, R]中 (R>=L) 。你可能需要改变树的根节点，所以结果应当返回修剪好的二叉搜索树的新的根节点。

【思路】

本题使用递归的方法非常简单：如果node为空，则返回NULL；如果node->val < L，则其左子树（包括自身）都应该被删除；如果node->val > R，则其右子树（包括自身）都应该被删除；其他情况，再次递归修剪其左右子树。

【代码】

python版本

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def trimBST(self, root, L, R):
        """
        :type root: TreeNode
        :type L: int
        :type R: int
        :rtype: TreeNode
        """
        if not root:
            return None
        if root.val < L:
            return self.trimBST(root.right, L, R)
        if root.val > R:
            return self.trimBST(root.left, L, R)
        root.left = self.trimBST(root.left, L, R)
        root.right = self.trimBST(root.right, L, R)
        return root

C++版本

/**
 * 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* trimBST(TreeNode* root, int L, int R) {
        if(!root)
            return NULL;
        if(root->val < L)
            return trimBST(root->right, L, R);
        if(root->val > R)
            return trimBST(root->left, L, R);
        root->left = trimBST(root->left, L, R);
        root->right = trimBST(root->right, L, R);
        return root;
    }
};

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2019-08-23，如有侵权请联系 cloudcommunity@tencent.com 删除

node.js