每天一道剑指offer-二叉树的下一个结点
原创
题目
每天一道剑指offer-二叉树的下一个结点
题目详述
给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
题目详解
思路
分析二叉树的下一个节点，一共有以下情况：
1.二叉树为空，则返回空；
2.节点右孩子存在，则设置一个指针从该节点的右孩子出发，一直沿着指向左子结点的指针找到的叶子节点即为下一个节点；
3.节点不是根节点。如果该节点是其父节点的左孩子，则返回父节点；否则继续向上遍历其父节点的父节点，重复之前的判断，返回结果。代码如下：
代码
/*
public class TreeLinkNode {
int val;
TreeLinkNode left = null;
TreeLinkNode right = null;
TreeLinkNode next = null;
TreeLinkNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public TreeLinkNode GetNext(TreeLinkNode pNode)
{
if(pNode == null)
return null;
if(pNode.right != null)
{//如果右子树不为空，那么中序遍历的下一个节点就是右子树的中的最左的那个节点
TreeLinkNode temp = pNode.right;
while(temp.left != null)
temp = temp.left;
return temp;
}
TreeLinkNode temp = pNode.next;//父节点
TreeLinkNode pre = pNode;//当前节点
while(temp != null)
{
if(temp.left == pre)
return temp;//如果当前节点pre是父节点的左子树，那么父节点就是下一个节点，终止循环
pre = temp;//如果不是，那么就pre指向父节点
temp = temp.next;//父节点指向自己的父节点，也就是向上一层移动
}
return temp;
}
}原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
评论
登录后参与评论
推荐阅读
目录