溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
本篇內容主要講解“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<root.Value,后繼節點要么是左子樹，要么是root自己
A，當在左子樹沒有找到，說明是root自己
B，找到了就在左子樹中
代碼實現
遞歸實現
/*** 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 []*TreeNodevar r []*TreeNodefor 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<len(r)-1;i++{if r[i]==p{return r[i+1]}}return nil}
到此，相信大家對“leetcode后繼者怎么實現”有了更深的了解，不妨來實際操作一番吧！這里是億速云網站，更多相關內容可以進入相關頻道進行查詢，關注我們，繼續學習！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
