洞察探讨小游戏SDK接入的最佳实践以及对企业跨平台开发的优势
694
2022-10-01
[leetcode] 669. Trim a Binary Search Tree
Description
Given a binary search tree and the lowest and highest boundaries as L and R, trim the tree so that all its elements lies in [L, R] (R >= L). You might need to change the root of the tree, so the result should return the new root of the trimmed binary search tree.
Example 1: Input:
1 / \ 0 2 L = 1 R = 2
Output:
1 \ 2
Example 2: Input:
3 / \ 0 4 \ 2 / 1 L = 1 R = 3
Output:
3 / 2 / 1
分析
题目的意思是:裁剪一颗二叉搜索树,使得二叉树的每个值的最小边界是L,最大边界是R。
二叉树首先是递归,递归的终止条件是节点为空,如果当前值小于L,则把左分支裁剪掉,返回右分支并递归;如果当前值大于R,则把右分支裁剪掉,返回左分支并且递归。否则,分别向左右分支递归,返回当前的节点。
/** * 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
参考文献
[LeetCode] Trim a Binary Search Tree 修剪一棵二叉搜索树
版权声明:本文内容由网络用户投稿,版权归原作者所有,本站不拥有其著作权,亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容,请联系我们jiasou666@gmail.com 处理,核实后本网站将在24小时内删除侵权内容。
发表评论
暂时没有评论,来抢沙发吧~