成品网站源码1688版本号,dedecms 安防监控行业网站模板,十大搞笑素材网站,网站建站平台排行榜题目#xff1a;
设计一个算法#xff0c;找出二叉搜索树中指定节点的“下一个”节点#xff08;也即中序后继#xff09;。
如果指定节点没有对应的“下一个”节点#xff0c;则返回null。
示例#xff1a; 输入: root [2,1,3], p 1 2 / \ 1 3 输出: 2 解题思路…题目
设计一个算法找出二叉搜索树中指定节点的“下一个”节点也即中序后继。
如果指定节点没有对应的“下一个”节点则返回null。
示例 输入: root [2,1,3], p 1 2 / \ 1 3 输出: 2 解题思路
我们可以中序遍历二叉树在找到p节点后做一个标记当遍历到它的后继时发现标记为真那么当前节点就是节点p的下一个节点返回即可。
源代码如下
class Solution {
public:TreeNode* resnullptr;bool flagfalse;//用来标记是否已经找到p若找到p则下一个遍历到的节点就是目标节点//中序遍历void inordered(TreeNode* root,TreeNode* p){if(root nullptr) return ;//当前节点为空直接返回inordered(root-left, p);//先遍历左子树if(res!nullptr) return;//如果res不为空说明已经找到目标节点//如果当前节点p则将flag更新if(root p){flagtrue;}//如果flag为真则说明当前节点就是目标节点else if(flag){//将节点赋值给res并返回resroot;return;}//继续遍历右子树inordered(root-right, p);}TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {if(rootnullptr) return nullptr;//对二叉树进行中序遍历在遍历过程中找目标节点inordered(root, p);return res;}
}; 简化一下
因为是中序遍历那么p的下一个节点一定是中序序列中第一个比p节点大的节点所以找到第一个比p大的节点即可。
源代码如下
class Solution {
public:TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {if(rootnullptr) return nullptr;TreeNode* resinorderSuccessor(root-left,p);if(res ! nullptr) return res;if(root-valp-val) return root;return inorderSuccessor(root-right,p);}
};
