面试题8：二叉树的下一个节点
题意：给定一棵二叉树的其中一个节点，请找出中序遍历序列的下一个节点。树中节点还有一个指向父节点的指针。
算法：模拟
思路：1）如果该节点有右子树，右子树最左边的节点为其后继节点。
2）如果该节点没有右子树，那么向上寻找father节点，找到第一个是father左儿子的节点，则其father节点为其后继。
时间复杂度：O(h)
TreeNode* inorderSuccessor(TreeNode* p) {
if(p -> right){
p = p -> right;
while(p -> left) p = p -> left;
return p;
}
while(p -> father && p == p -> father -> right) p = p -> father;
return p -> father;
}
面试题8：二叉树的下一个节点 题意：给定一棵二叉树的其中一个节点，请找出中序遍历序列的下一个节点。树中节点还有一个...
《剑指offer》面试题8：二叉树的下一个节点 题目：给定一颗二叉树和其中的一个节点，如何找出中序遍历序列的下一个...
面试题58：二叉树的下一个节点给定一个二叉树和其中一个节点，如何找到中序遍历顺序的下一个节点？树中的节点除了有两个...
本系列导航：剑指offer（第二版）java实现导航帖 面试题8：二叉树的下一个节点 题目要求：给定二叉树和其中一...
找到中序遍历二叉树下一个节点分析二叉树的下一个节点，一共有以下情况：1.二叉树为空，则返回空；2.节点右孩子存在，...
今天学习的是二叉树中的算法题目：填充每个节点的下一个右侧节点指针。 题目介绍 给定一个满二叉树（所有叶子节点都在同...
填充每个节点的下一个右侧节点指针 II 题目描述：给定一个二叉树：struct Node { int val; ...
题目 给定一个二叉树与其中一个节点（目标节点），找到中序遍历中的下一个节点(子节点中包含父节点的引用) 题解 解法...
【leetcode-树】填充每个节点的下一个右侧节点指针 给定一个完美二叉树，其所有叶子节点都在同一层，每个父节点...
题目描述 给定一个二叉树 填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，...
本文标题：面试题8：二叉树的下一个节点
本文链接：https://www.haomeiwen.com/subject/fpnzpctx.html
网友评论