深圳市建设交易中心网站首页,汽车专业科技网站建设,河南智能网站建设哪家好,5分钟宣传片报价明细Problem: 面试题 04.06. 后继者 文章目录 题目描述思路解题方法复杂度Code 题目描述
设计一个算法#xff0c;找出二叉搜索树中指定节点的“下一个”节点#xff08;也即中序后继#xff09;。
如果指定节点没有对应的“下一个”节点#xff0c;则返回null。 思路 由于题… Problem: 面试题 04.06. 后继者 文章目录 题目描述思路解题方法复杂度Code 题目描述
设计一个算法找出二叉搜索树中指定节点的“下一个”节点也即中序后继。
如果指定节点没有对应的“下一个”节点则返回null。 思路 由于题意是找出一个在二叉搜索树中给定的节点的后继节点按示例意思可知道为求二叉搜索树中序遍历递增序列中给定一个节点的相邻的下一个更大的值进一步分析可得为利用二叉搜索树中序遍历的得出递增序列再在此基础上求取一给定值的下一个比给定值大的值 解题方法 1.定义两个成员变量一个用于记录在中序遍历过程中当前节点是否为指定节点假设为comming 返回类型为boolean一个用于返回最后的结果假设为succession 返回类型为TreeNode由于本解法用到递归处理二叉树的中序遍历所以定义两个成员变量用于辅助记录 2.中序遍历查找指定节点若当前节点是指定节点则将comming修改为true当再在递归过程中判断comming为true时则表示当前节点为指定节点的下一个节点将当前节点指向succession最后返回即可。 3.注意在递归过程中若判断succession不为null时说明已经找到后继节点则可以提前结束递归 复杂度
时间复杂度: O ( n ) O(n) O(n) 空间复杂度: O ( n ) O(n) O(n) Code /*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode(int x) { val x; }* }*/
class Solution {//Time Complexity: O(n)//Space Complexity: O(n)//用与记录下一个private boolean comming false;private TreeNode successor null;public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {inOrder(root,p);return successor;}private void inOrder(TreeNode root, TreeNode p) {if (root null) {return;}inOrder(root.left,p);if (successor ! null) {return;}//如果上一个节点是指定节点if (comming true) {successor root;comming false;}//入果当前节点是指点节点//将comming设置为trueif (root p) {comming true;}inOrder(root.right,p);}
}
