算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选 ！今天和大家聊的问题叫做 二叉搜索树中的中序后继，我们先来看题面：https:///problems/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. The successor of a node p is the node with the smallest key greater than p.val.
给你一个二叉搜索树和其中的某一个结点，请你找出该结点在树中顺序后继的节点。结点 p 的后继是值比 p.val 大的结点中键值最小的结点。示例输入: root = [2,1,3], p = 1
输出: 2
解析: 这里 1 的顺序后继是 2。
请注意 p 和返回值都应是 TreeNode 类型。 解题这道题让我们求二叉搜索树的某个节点的中序后继节点，那么根据 BST 的性质知道其中序遍历的结果是有序的，博主最先用的方法是用迭代的中序遍历方法，然后用一个 bool 型的变量b，初始化为 false，进行中序遍历，对于遍历到的节点，首先看如果此时b已经为 true，说明之前遍历到了p，那么此时返回当前节点，如果b仍为 false，看遍历到的节点和p是否相同，如果相同，此时将b赋为 true，那么下一个遍历到的节点就能返回了，参见代码如下：class Solution {
public:
TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
stack<TreeNode*> s;
bool b = false;
TreeNode *t = root;
while (t || !s.empty()) {
while (t) {
s.push(t);
t = t->left;
}
t = s.top(); s.pop();
if (b) return t;
if (t == p) b = true;
t = t->right;
}
return NULL;
}
}; 好了，今天的文章就到这里，如果觉得有所收获，请顺手点个在看或者转发吧，你们的支持是我最大的动力 。
|
