【算法题解】61. 求二叉搜索树的后继者

❝

这是一道 「中等难度」 的题
https://leetcode.cn/problems/successor-lcci/

❞

题目

设计一个算法，找出二叉搜索树中指定节点的“下一个”节点（也即中序后继）。

如果指定节点没有对应的“下一个”节点，则返回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

解法一：中序遍历

二叉搜索树中某一个节点的后继就是指其中序后继，即求中序遍历中给定节点的下一个节点是什么。

如中序遍历为：，那么节点3 的后继就是节点4，节点4 的后继就是节点5，而节点6 没有后继所以是 null。

根据题意，最简单的思路就是根据 「中序遍历」 的规则把给定的二叉搜索树走一遍，如果遇到了给定的 「节点p」，那么下一步遍历到的节点就是后继者。

代码实现

Java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    boolean found = false;
    TreeNode ans;
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        dfs(root, p);
        return ans;
    }

    private void dfs(TreeNode node, TreeNode p){
        if(node == null || ans != null){
            return;
        }

        dfs(node.left, p);

        if(found && ans == null){
            ans = node;

        }else if(node.val == p.val){
            found = true;
        }
        
        dfs(node.right, p);
    }

 
}

Go

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func inorderSuccessor(root *TreeNode, p *TreeNode) *TreeNode {

    found := false
    var ans *TreeNode;

    var dfs func(node *TreeNode, p *TreeNode)

    dfs = func(node *TreeNode, p *TreeNode) {
        if node == nil {
            return
        }

        dfs(node.Left, p)

        if found && ans == nil {
            ans = node
        }else if node.Val == p.Val {
            found = true
        }

        dfs(node.Right, p)
    }

    dfs(root, p)

    return ans
}

可以看到上面的实现完全忽略了二叉搜索树 「可以搜索」 的特性，一个一个的去找，时间复杂度为。这不是一个好的算法。

解法二：利用搜索特性

根据二叉树搜索树的可搜索特性，后继者有两种情况：

如果指定节点包含右子树，那么后继者肯定在其右子树当中，且是右子树中最左边的那个节点。
如果指定节点不包含右子树，那么从根节点开始找指定节点的时候，所有大于指定节点的位置都可能是后继者，记录下来取最小的那个即可。

如下图所示：节点4 包含右子树，所以其后继为右子树中最左边的节点，即节点5。

如下图所示：节点3 没有右子树，所以其后继为所有经过的根节点中，所有比3大的节点中的最小值，即节点4。因为节点2 小于节点3，所以直接排除。

代码实现

Java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        if(root == null){
            return null;
        }

       
        TreeNode ans = null;

        // 右子树不空
        if(p.right != null){
            ans = p.right;
            while(ans.left != null){
                ans = ans.left;
            }   
            return ans;
        }


        // 右子树为空
        TreeNode pos = root;
        while(pos != null){
            // 往左走的时候，经过的每一个根节点可能是后继
            if(p.val < pos.val){
                if(ans == null){
                    ans = pos;
                }else if(pos.val < ans.val){
                    ans = pos;
                }
                pos = pos.left;
            }else if(p.val > pos.val){
                pos = pos.right;
            }else{
                // 找到了
                // 右子树为空，后继者为从根节点遍历到 p 的时候，val大于p的最小值。 
                return ans;

            }
        }

        return null;
    }
}

Go

/**
 * 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 {
        return nil
    }

    var ans *TreeNode
    if p.Right != nil {
        ans = p.Right
        for ans.Left != nil {
            ans = ans.Left
        }
        return ans
    }

    pos := root
    for pos != nil {
        if p.Val < pos.Val {
            if ans == nil {
                ans = pos
            }else if pos.Val < ans.Val {
                ans = pos
            }
            pos = pos.Left
        }else if p.Val > pos.Val{
            pos = pos.Right
        }else {
            // 找到了
            return ans
        } 
    }

    return nil
}