二叉树2---修剪二叉树线索树 曾经终败给现在 2022-05-25 11:24 170阅读 0赞 1、题目: -------------------- 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 2、解答:如果头结点的值小于L,由二叉排序树的特点可知,只用在二叉树的右边进行;与之相反,只需要在右边遍历;若头结点的值在L,R之间,则需要递归的进行。 3、C++代码: class Solution { public: TreeNode* trimBST(TreeNode* root, int L, int R) { if(root == NULL) 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; } }; python代码: class Solution: def trimBST(self, root, L, R): """ :type root: TreeNode :type L: int :type R: int :rtype: TreeNode """ if root == None: 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
相关 线索二叉树 使用二叉树作为存储结构时,只能找到结点的左、右孩子的信息,而不能直接得到结点的前驱和后继的信息; 在有n个结点的二叉树中有n+1个空指针,利用这n+1个空指保存前驱和后继的信 小灰灰/ 2022年06月10日 06:18/ 0 赞/ 215 阅读
相关 线索二叉树 线索化二叉树相对于之前的树的遍历,在树的定义上增加了两个值,一个是ltag,另外一个是rtag。 ltag代表着这个节点的是否有右孩子,如果有,则ltag=1,p->lchi 以你之姓@/ 2022年06月09日 01:13/ 0 赞/ 187 阅读
相关 线索二叉树 在找线索二叉树的过程中,这篇博客很值得推荐;[http://waret.iteye.com/blog/709779][http_waret.iteye.com_blog_709 我就是我/ 2022年06月04日 03:21/ 0 赞/ 195 阅读
相关 线索二叉树 二叉树的链式存储如下图, ![Image 1][] 不难发现,图中所示的左—右指针表示中,有一半以上的指针是空的。事实上,所有包括n个结点的二叉树的这种表示中,每个结 秒速五厘米/ 2022年05月29日 00:18/ 0 赞/ 156 阅读
相关 二叉树2---修剪二叉树线索树 1、题目: -------------------- Given a binary search tree and the lowest and highest bound 曾经终败给现在/ 2022年05月25日 11:24/ 0 赞/ 171 阅读
相关 线索二叉树 线索二叉树提出的原因: 在普通二叉树中,每个结点都有左右两个指针域,这些指针域都指向结点类型的数据对象,当二叉树稀疏时,很多结点的左右两个指针域就显得浪费存储空间了。因此,提 待我称王封你为后i/ 2022年03月15日 13:24/ 0 赞/ 249 阅读
相关 线索二叉树 本文主要介绍线索二叉树和树、二叉树、森林三者之间的相互转换。 对于线索二叉树,这里只做简单介绍,着重还是要理解上篇博文中二叉树的各种遍历算法。 线索二叉树 基本概念 旧城等待,/ 2022年02月23日 08:36/ 0 赞/ 215 阅读
相关 线索二叉树 什么是线索二叉树? 遍历二叉树是以一定的规则将二叉树中的结点排列成一个线性序列,从而等到二叉树的各种遍历序列,其实质是对一个非线性操作进行线性化操作,使这个访问序列中的每 女爷i/ 2022年01月23日 08:15/ 0 赞/ 246 阅读
相关 线索二叉树 package com.tree; import java.util.concurrent.SynchronousQueue; / 红太狼/ 2021年10月15日 02:37/ 0 赞/ 293 阅读
相关 线索二叉树 Overview 将二叉树中没有子节点的节点称为空指针域,利用二叉树的空指针域,按照前中后某种遍历方式存放对应的前驱节点,后驱节点(这种附加指针称为“线索”)。二叉树的空 矫情吗;*/ 2021年10月01日 09:34/ 0 赞/ 344 阅读
还没有评论,来说两句吧...