【剑指Offer|C++】面试题8：寻找二叉树的下一个节点|上一个节点-创新互联

题目：给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。

创新互联长期为超过千家客户提供的网站建设服务，团队从业经验10年，关注不同地域、不同群体，并针对不同对象提供差异化的产品和服务；打造开放共赢平台，与合作伙伴共同营造健康的互联网生态环境。为资源企业提供专业的成都网站设计、成都网站建设，资源网站改版等技术服务。拥有10多年丰富建站经验和众多成功案例,为您定制开发。

题目算是比较新颖的了
题解：

//结构体定义
struct BinaryTreeNode
{int value;
	BinaryTreeNode* left;
	BinaryTreeNode* right;
	BinaryTreeNode* parent;
}

//找下一个节点
BinaryTreeNode* GetNext(BinaryTreeNode* node)
{//特殊处理
	if(node == nullptr)
		return nullptr;
	
	BinaryTreeNode* next = nullptr;//定义要返回的结果指针
	if(node->right != nullptr)//有右子树：找到右子树的最左节点
	{BinaryTreeNode* pRight = node->right;
		while(pRight ->left != nullptr)
		{	pRight = pRight->left;
		}
		next = pRight;
	}
	else if(node->parent != nullptr)//非根节点
	{BinaryTreeNode* current = node;
		BinaryTreeNode* pParent = node->parent;
		while(pParent != nullptr && current == pPrent->right)//没有右子树且他还是父节点的右子节点：向上遍历直到找到一个节点是父节点的左子节点，该父节点就是要找的这个节点
		{	current = pParent;
			pParent= pParent->parent;
		}
		next = pParent;//没有右子树且是父节点的左子节点：该节点的父节点就是要找的节点
	}
}

拓展：寻求上一个节点

跟上述思路相反：
如果有左子树，即为左子树的最右子节点。
如果无左子树，如果本身为父节点的的右子节点，即为父节点
为父节点的左子节点，即为祖父节点

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

本文题目：【剑指Offer|C++】面试题8：寻找二叉树的下一个节点|上一个节点-创新互联
本文路径：http://6mz.cn/article/dcojgo.html