【剑指Offer】58:二叉树的下一个结点
2024-09-06 14:17:31
题目描述
给定一个二叉树和其中的一个结点,请找出中序遍历顺序的下一个结点并且返回。注意,树中的结点不仅包含左右子结点,同时包含指向父结点的指针。
题解一:递归
//既然给了二叉树的某个结点,且二叉树存储着指向父结点的指针(next), //那我们可以先找到根节点,再对树进行中序遍历,最后根据中序遍历结果找到给定结点的下一结点 private static ArrayList<TreeLinkNode> linkNodes = new ArrayList<>(); public static TreeLinkNode GetNext(TreeLinkNode pNode){ TreeLinkNode root = pNode; //找到父节点 while(root.next != null){ root = root.next; } InOrder(root); for(int i=0;i<linkNodes.size();i++){ if(pNode == linkNodes.get(i)){ if(i==linkNodes.size()-1){ return null; } return linkNodes.get(i+1); } } return null; } public static void InOrder(TreeLinkNode pNode){ if(pNode==null){ return; } InOrder(pNode.left); linkNodes.add(pNode); InOrder(pNode.right); }
题解二:分情况讨论
//1、给定节点有right,就返回right节点子树最左节点; //2、没右子树,一路向上找,返回子节点为父节点左节点的父节点,如果没有就返回null。 public static TreeLinkNode GetNext01(TreeLinkNode node) { if(node==null){ return null; } //如果有右子树,则找右子树的最左节点 if(node.right!=null){ node = node.right; while(node.left!=null){ node = node.left; } return node; } //没右子树,则找第一个当前节点是父节点左孩子的节点 while(node.next!=null){ if(node.next.left==node){ return node.next; } node = node.next; } //退到了根节点仍没找到,则返回null return null; }
初始化树:
public static class TreeLinkNode{ int val; TreeLinkNode left = null; TreeLinkNode right = null; TreeLinkNode next = null; TreeLinkNode(int val) { this.val = val; } }
测试:
public static void main(String[] args) { int[] tree={8,6,10,5,7,9,11}; TreeLinkNode linkNode = createBinTree(tree); TreeLinkNode getNext = GetNext(linkNode); System.out.println(getNext.val); } 输出: 9
最新文章
- VS2013.3 &; VS2014 任务资源管理器
- DSP using MATLAB 示例Example3.9
- android之外部文件存储和读取
- swift-03-构造器(Designated&;&;Convenience)
- Java并发编程-并发工具包(java.util.concurrent)使用指南(全)
- 【学习笔记】【C语言】函数
- JavaScript console 用法大全
- Swift的字符串String是值类型
- Visual Studio 2015 企业版 官方中文版.iso
- The working copy xxxx needs to be upgraded to Subversion 1.7.
- linux ubuntu 浏览器 字 字体 虚 解决办法
- javascript中处理引号编码&;#034;
- iOS--通过MOB平台实现第三方登录与分享
- java构造代码块,构造函数和普通函数的区别和调用时间
- 今天打补丁出问题了,害得我组长被扣了1k奖金。
- springcloud(六):配置中心(一)
- Puppeteer之大屏批量截图
- Codeforces Beta Round #51 D. Beautiful numbers(数位dp)
- jQ常用选择器
- UVALive 6906 Cluster Analysis 并查集