2022-8-16 剑指offer-二叉树
2022/8/16 23:27:32
本文主要是介绍2022-8-16 剑指offer-二叉树,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
剑指 Offer II 053. 二叉搜索树中的中序后继
难度中等给定一棵二叉搜索树和其中的一个节点 p
,找到该节点在树中的中序后继。如果节点没有中序后继,请返回 null
。
节点 p
的后继是值比 p.val
大的节点中键值最小的节点,即按中序遍历的顺序节点 p
的下一个节点。
1 /** 2 * Definition for a binary tree node. 3 * public class TreeNode { 4 * int val; 5 * TreeNode left; 6 * TreeNode right; 7 * TreeNode(int x) { val = x; } 8 * } 9 */ 10 class Solution { 11 ArrayDeque<TreeNode> stack; 12 public TreeNode inorderSuccessor(TreeNode root, TreeNode p) { 13 stack=new ArrayDeque<>(); 14 return dfs(root,p); 15 } 16 17 public TreeNode dfs(TreeNode root,TreeNode p){ 18 // for (TreeNode x:stack){ 19 // System.out.print(x.val+" "); 20 // } 21 if (root==null) return null; 22 if (root.val==p.val){ 23 if (root.right!=null){ 24 TreeNode node=root.right; 25 while (node.left!=null) node=node.left; 26 return node; 27 } 28 while (!stack.isEmpty()){ 29 TreeNode t=stack.pop(); 30 if (t!=null&&t.val>p.val) return t; 31 } 32 return null; 33 }else if (root.val>p.val){ 34 stack.push(root); 35 return dfs(root.left,p); 36 }else{ 37 stack.push(root); 38 return dfs(root.right,p); 39 } 40 } 41 }
思路:记录当前节点和前继节点,中序遍历,或者利用搜索树的性质。
这篇关于2022-8-16 剑指offer-二叉树的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?
- 2024-05-09企业src漏洞挖掘-有意思的命令执行