本篇内容主要讲解“leetcode后继者怎么实现”,感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷,实用性强。下面就让小编来带大家学习“leetcode后继者怎么实现”吧!
创新互联建站专注于饶平网站建设服务及定制,我们拥有丰富的企业做网站经验。 热诚为您提供饶平营销型网站建设,饶平网站制作、饶平网页设计、饶平网站官网定制、成都小程序开发服务,打造饶平网络公司原创品牌,更为您提供饶平网站排名全网营销落地服务。
设计一个算法,找出二叉搜索树中指定节点的“下一个”节点(也即中序后继)。
如果指定节点没有对应的“下一个”节点,则返回null。
示例 1:
输入: root = [2,1,3], p = 1
2
/ \
1 3
输出: 2
示例 2:
输入: root = [5,3,6,2,4,null,null,1], p = 6
5
/ \
3 6
/ \
2 4
/
1
输出: null
解题思路:
1,类似二叉搜索树的查找,区别是查找当前值的下一个节点
2,如果p.Value>=root.Value,后继节点一定在右子树
3,如果p.Value A,当在左子树没有找到,说明是root自己 B,找到了就在左子树中 代码实现 递归实现 非递归实现 到此,相信大家对“leetcode后继者怎么实现”有了更深的了解,不妨来实际操作一番吧!这里是创新互联网站,更多相关内容可以进入相关频道进行查询,关注我们,继续学习!/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func inorderSuccessor(root *TreeNode, p *TreeNode) *TreeNode {
if root==nil || p==nil{
return nil
}
if root.Val<=p.Val{
return inorderSuccessor(root.Right,p)
}
p0:=inorderSuccessor(root.Left,p)
if p0!=nil{
return p0
}
return root
}
func inorderSuccessor(root *TreeNode, p *TreeNode) *TreeNode {
if root==nil || p==nil{
return nil
}
var q []*TreeNode
var r []*TreeNode
for len(q)>0 || root!=nil{
for root!=nil && root.Left!=nil{
q=append(q,root)
root=root.Left
}
fmt.Println(len(q),root,root==nil)
if root==nil{
l:=len(q)
if l>0{
root=q[l-1]
q=q[:l-1:l-1]
//fmt.Println(len(q),root,root==nil)
r=append(r,root)
root=root.Right
}
}else{
r=append(r,root)
//fmt.Println(len(q),root,root.Right)
root=root.Right
}
}
for i:=0;i
if r[i]==p{
return r[i+1]
}
}
return nil
}
分享标题:leetcode后继者怎么实现
网页URL:http://cdkjz.cn/article/pdoiei.html