LeetCode 题解

积跬步，至千里。

后继者

分类：程序员面试金典题解 标签： 树 深度优先搜索 发布于：2020-05-20 ID：4.06

题目描述

来源于 https://leetcode-cn.com/

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

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

解法：

中序遍历，寻找第一个值大于 p 的节点即可。

class Solution {
public:
    TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
        if(root == nullptr){
            return nullptr;
        }
        TreeNode* ret = inorderSuccessor(root->left, p);
        if(ret != nullptr){
            return ret;
        }
        if(root->val > p->val){
            return root;
        }
        return inorderSuccessor(root->right, p);
    }
};

中序遍历，保存前一个节点为 prev，当前节点为 node，当 prev == p 的时候，返回 node 节点。

class Solution {
public:
    TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
        if(traversal(root, p)){
            return prev;
        }
        return nullptr;
    }

    bool traversal(TreeNode* node, TreeNode* p){
        if(node == nullptr) return false;

        bool stop = traversal(node->left, p);
        if(stop){
            return true;
        }

        if(p == prev){
            prev = node;
            return true;
        }

        prev = node;

        stop = traversal(node->right, p);
        if(stop == true){
            return true;
        }

        return false;
    }
private:
    TreeNode* prev = nullptr;
};