[LeetCode] 285. Inorder Successor in BST

focusj 發布于2019-08-16 13:45 / 1805人閱讀

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;
        }
    }
}

GPU云服務器云服務器 Successor Inorder v285 BST

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/72286.html

LeetCode[285] Inorder Successor in BST

摘要：復雜度思路找的是比這個大的最小值。代碼如果是小于等于的值，就要往右移動比大的值都可能是，所以要保留 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: ...

oneasp 2019-08-14 15:02 評論0 收藏0
【LeetCode 二叉樹專項】二叉搜索樹中的中序后繼（285）

摘要：解法二迭代中序遍歷分析作者二叉搜索樹的中序后繼是中序遍歷中當前節點之后最小的節點。文章目錄 1. 題目1.1 示例1.2 說明1.3 限制 2....

ccj659 2021-11-24 09:39 評論0 收藏0
[Leetcode] Inorder Successor in BST 二叉搜索樹中序下一個

摘要：所以我們要找的上面，實際上是從目標節點向根節點回溯時，第一個比目標節點大的節點。 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...

marek 2019-08-14 12:36 評論0 收藏0
[Leetcode] Binary Search Tree Iterator 二叉搜素樹迭代器

摘要：代碼先找到第一個節點，并把路徑入棧棧為空時不再有下一個棧頂是待返回元素如果該元素有右節點，把它的右節點及右節點的所有左邊節點都壓入棧中 Binary Search Tree Iterator 最新更新：https://yanjia.me/zh/2019/02/... Implement an iterator over a binary search tree (BST). Your...

shixinzhang 2019-08-14 12:36 評論0 收藏0
LeetCode 272 Closest Binary Tree Traversal II 解題思路

摘要：原題網址題意在二叉搜索樹當中找到離最近的個數。解題思路由于二叉搜索數的中序遍歷是有序的，比如例子中的樹，中序遍歷為。原題網址：https://leetcode.com/problems... Given a non-empty binary search tree and a target value, find?k?values in the BST that are closes...

Youngdze 2019-08-16 13:26 評論0 收藏0