【剑指Offer】8. 二叉树的下一个结点


题目描述

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

public class TreeLinkNode {

int val;
TreeLinkNode left = null;
TreeLinkNode right = null;
TreeLinkNode next = null;

TreeLinkNode(int val) {
this.val = val;
}
}

解题思路
判断右节点是否为空

① 如果一个节点的右子树不为空,那么该节点的下一个节点是右子树的最左节点;
② 否则,向上找第一个左链接指向的树包含该节点的祖先节点。

/*
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.right != null) {
TreeLinkNode node = pNode.right;
while(node.left != null)
node = node.left;
return node;
}else {
while(pNode.next != null) {
TreeLinkNode parens = pNode.next;
if(parens.left == pNode)
return parens;
pNode = pNode.next;
}
}
return null;
}
}

借助列表递归

static  ArrayList<TreeLinkNode> a=new ArrayList<>();
public static void InOrder(TreeLinkNode pRoot){
if (pRoot != null) {
InOrder(pRoot.left);
a.add(pRoot);
InOrder(pRoot.right);
}
}

public TreeLinkNode GetNext(TreeLinkNode pNode)
{
TreeLinkNode p=pNode;
int i;
while (pNode.next!=null)
{
pNode=pNode.next;

}
InOrder(pNode);
for( i=0;i<a.size();i++)
{
if(p==a.get(i))
{
return i == a.size()-1?null:a.get(i+1);
}
}
return null;

}

关注博主即可阅读全文


原创:https://www.panoramacn.com
源码网提供WordPress源码,帝国CMS源码discuz源码,微信小程序,小说源码,杰奇源码,thinkphp源码,ecshop模板源码,微擎模板源码,dede源码,织梦源码等。

专业搭建小说网站,小说程序,杰奇系列,微信小说系列,app系列小说

【剑指Offer】8. 二叉树的下一个结点

免责声明,若由于商用引起版权纠纷,一切责任均由使用者承担。

您必须遵守我们的协议,如果您下载了该资源行为将被视为对《免责声明》全部内容的认可-> 联系客服 投诉资源
www.panoramacn.com资源全部来自互联网收集,仅供用于学习和交流,请勿用于商业用途。如有侵权、不妥之处,请联系站长并出示版权证明以便删除。 敬请谅解! 侵权删帖/违法举报/投稿等事物联系邮箱:2640602276@qq.com
未经允许不得转载:书荒源码源码网每日更新网站源码模板! » 【剑指Offer】8. 二叉树的下一个结点
关注我们小说电影免费看
关注我们,获取更多的全网素材资源,有趣有料!
120000+人已关注
分享到:
赞(0) 打赏

评论抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

您的打赏就是我分享的动力!

支付宝扫一扫打赏

微信扫一扫打赏