Java 求解修剪二叉搜索树
2021/10/31 17:09:58
本文主要是介绍Java 求解修剪二叉搜索树,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
文章目录
- 一、题目
- 二、题解
- 三、代码
- 四、总结
一、题目
给你二叉搜索树的根节点 root ,同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树,使得所有节点的值在[low, high]中。修剪树不应该改变保留在树中的元素的相对结构(即,如果没有被移除,原有的父代子代关系都应当保留)。 可以证明,存在唯一的答案。
所以结果应当返回修剪好的二叉搜索树的新的根节点。注意,根节点可能会根据给定的边界发生改变。
二、题解
发现节点0并不符合区间要求,那么将节点0的右孩子 节点2 直接赋给 节点3的左孩子就可以了(就是把节点0从二叉树中移除)
(1)确定递归函数及返回值
因为是要遍历整棵树,做修改,其实不需要返回值也可以,我们也可以完成修剪(其实就是从二叉树中移除节点)的操作。
但是有返回值,更方便,可以通过递归函数的返回值来移除节点。
(2)确定递归终止条件
修剪的操作并不是在终止条件上进行的,所以就是遇到空节点返回就可以了
(3)确定单层递归的逻辑
如果root(当前节点)的元素小于low的数值,那么应该递归右子树,并返回右子树符合条件的头结点。
if (root.val < low) { //寻找符合区间[low,high]的节点 TreeNode right = trimBST(root.right, low, high); return right; }
如果root(当前节点)的元素大于high的,那么应该递归左子树,并返回左子树符合条件的头结点
if (root.val > high) { //寻找符合区间[low,high]的节点 TreeNode left = trimBST(root.left, low, high); return left; }
接下来要将下一层处理完左子树的结果赋给 root.left
,处理完右子树的结果赋给 root.right
。
//root.left接入符合条件的左孩子 root.left = trimBST(root.left, low, high); //root.right接入符合条件的右孩子 root.right = trimBST(root.right, low, high);
三、代码
class Solution { public TreeNode trimBST(TreeNode root, int low, int high) { if (root == null) { return null; } if (root.val < low) { //寻找符合区间[low,high]的节点 TreeNode right = trimBST(root.right, low, high); return right; } if (root.val > high) { //寻找符合区间[low,high]的节点 TreeNode left = trimBST(root.left, low, high); return left; } //root.left接入符合条件的左孩子 root.left = trimBST(root.left, low, high); //root.right接入符合条件的右孩子 root.right = trimBST(root.right, low, high); return root; } }
四、总结
这篇关于Java 求解修剪二叉搜索树的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-02springboot项目无法注册到nacos-icode9专业技术文章分享
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)