算法的重要性,，我就不多說了吧，想去大廠,，就必須要經(jīng)過基礎(chǔ)知識和業(yè)務邏輯面試+算法面試,。所以，為了提高大家的算法能力，這個公眾號后續(xù)每天帶大家做一道算法題,，題目就從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.
給你一個二叉搜索樹和其中的某一個結(jié)點,，請你找出該結(jié)點在樹中順序后繼的節(jié)點,。結(jié)點 p 的后繼是值比 p.val 大的結(jié)點中鍵值最小的結(jié)點。示例輸入: root = [2,1,3], p = 1
輸出: 2
解析: 這里 1 的順序后繼是 2,。
請注意 p 和返回值都應是 TreeNode 類型,。 解題這道題讓我們求二叉搜索樹的某個節(jié)點的中序后繼節(jié)點，那么根據(jù) BST 的性質(zhì)知道其中序遍歷的結(jié)果是有序的,，博主最先用的方法是用迭代的中序遍歷方法,，然后用一個 bool 型的變量b，初始化為 false,，進行中序遍歷,，對于遍歷到的節(jié)點，首先看如果此時b已經(jīng)為 true,，說明之前遍歷到了p,，那么此時返回當前節(jié)點，如果b仍為 false,，看遍歷到的節(jié)點和p是否相同,，如果相同，此時將b賦為 true,，那么下一個遍歷到的節(jié)點就能返回了,，參見代碼如下：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;
}
}; 好了，今天的文章就到這里,，如果覺得有所收獲,，請順手點個在看或者轉(zhuǎn)發(fā)吧，你們的支持是我最大的動力 ,。
|
