【LeetCode】后继者 Java 题解

2022 年 5 月 16 日
本文字数：816 字
阅读完需：约 3 分钟

题目描述

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

如果指定节点没有对应的“下一个”节点，则返回 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
来源：力扣（LeetCode）链接：https://leetcode.cn/problems/successor-lcci著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

思路分析

今天的算法题目是二叉树题目，题目要求找二叉搜索树中指定节点的“下一个”节点（也即中序后继）。由于树的结构不能直接查找，我们可以先对树进行遍历，然后进行遍历查找。实现代码如下，供参考。

通过代码

/** * Definition for a binary tree node. * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode(int x) { val = x; } * } */class Solution {    List<Integer> list = new ArrayList<>();
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {        dfs(root, list);        TreeNode ans = new TreeNode();        int n = list.size();        int i = 0;        while (i < n) {            if (list.get(i) == p.val) {                break;            }            i++;        }
        if (i + 1 < n) {            ans = new TreeNode(list.get(i + 1));        } else {            ans = null;        }
        return ans;    }
    private void dfs(TreeNode root, List<Integer> list) {        if (root == null) {            return;        }
        dfs(root.left, list);        list.add(root.val);        dfs(root.right, list);    }}