資訊專(zhuān)欄INFORMATION COLUMN
Problem
Given a binary search tree and a node in it, find the in-order successor of that node in the BST.
Note: If the given node has no in-order successor in the tree, return null.
Example 1:
Input: root = [2,1,3], p = 1 2 / 1 3 Output: 2
Example 2:
Input: root = [5,3,6,2,4,null,null,1], p = 6
5
/
3 6
/
2 4
/
1
Output: null
Solution
class Solution {
public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
//successor must be larger then the node itself, so:
//if p is in root.left, root can be the successor, null cannot be
//if p is in root.right, root can not be the successor, null can be
if (root == null) return null;
if (root.val <= p.val) {
return inorderSuccessor(root.right, p);
} else {
TreeNode leftRes = inorderSuccessor(root.left, p);
if (leftRes == null) return root;
return leftRes;
}
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/72286.html
摘要：復(fù)雜度思路找的是比這個(gè)大的最小值。代碼如果是小于等于的值，就要往右移動(dòng)比大的值都可能是，所以要保留 LeetCode[285] Inorder Successor in BST Given a binary search tree and a node in it, find the in-order successor of that node in the BST. Note: ...
摘要：解法二迭代中序遍歷分析作者二叉搜索樹(shù)的中序后繼是中序遍歷中當(dāng)前節(jié)點(diǎn)之后最小的節(jié)點(diǎn)。 文章目錄 1. 題目1.1 示例1.2 說(shuō)明1.3 限制 2....
摘要：所以我們要找的上面，實(shí)際上是從目標(biāo)節(jié)點(diǎn)向根節(jié)點(diǎn)回溯時(shí)，第一個(gè)比目標(biāo)節(jié)點(diǎn)大的節(jié)點(diǎn)。 Inorder Successor in BST Given a binary search tree and a node in it, find the in-order successor of that node in the BST. Note: If the given node has n...
摘要：代碼先找到第一個(gè)節(jié)點(diǎn)，并把路徑入棧棧為空時(shí)不再有下一個(gè)棧頂是待返回元素如果該元素有右節(jié)點(diǎn)，把它的右節(jié)點(diǎn)及右節(jié)點(diǎn)的所有左邊節(jié)點(diǎn)都?jí)喝霔Ｖ? Binary Search Tree Iterator 最新更新：https://yanjia.me/zh/2019/02/... Implement an iterator over a binary search tree (BST). Your...
摘要：原題網(wǎng)址題意在二叉搜索樹(shù)當(dāng)中找到離最近的個(gè)數(shù)。解題思路由于二叉搜索數(shù)的中序遍歷是有序的，比如例子中的樹(shù)，中序遍歷為。 原題網(wǎng)址：https://leetcode.com/problems... Given a non-empty binary search tree and a target value, find?k?values in the BST that are closes...
閱讀 1449·2023-04-26 01:58
閱讀 2326·2021-11-04 16:04
閱讀 1810·2021-08-31 09:42
閱讀 1804·2021-07-25 21:37
閱讀 1091·2019-08-30 15:54
閱讀 2120·2019-08-30 15:53
閱讀 3078·2019-08-29 13:28
閱讀 2722·2019-08-29 10:56
