广州市住房和建设水务局网站,建筑行业资讯网站,网站定制开发 广州,抖音代运营是啥题目
给定一棵二叉搜索树和它的一个节点p#xff0c;请找出按中序遍历的顺序该节点p的下一个节点。假设二叉搜索树中节点的值都是唯一的。例如#xff0c;在图8.9的二叉搜索树中#xff0c;节点8的下一个节点是节点9#xff0c;节点11的下一个节点是null。
分析#xf…题目
给定一棵二叉搜索树和它的一个节点p请找出按中序遍历的顺序该节点p的下一个节点。假设二叉搜索树中节点的值都是唯一的。例如在图8.9的二叉搜索树中节点8的下一个节点是节点9节点11的下一个节点是null。
分析时间复杂度On的解法
解决这个问题的最直观的思路就是采用二叉树的中序遍历。可以用一个布尔变量found来记录已经遍历到节点p。该变量初始化为false遍历到节点p就将它设为true。在这个变量变成true之后遍历到的第1个节点就是要找的节点。
解时间复杂度On的解法
public class Test {public static void main(String[] args) {TreeNode node1 new TreeNode(1);TreeNode node2 new TreeNode(2);TreeNode node3 new TreeNode(3);TreeNode node4 new TreeNode(4);TreeNode node5 new TreeNode(5);TreeNode node6 new TreeNode(6);node4.left node2;node4.right node5;node2.left node1;node2.right node3;node5.right node6;TreeNode result inorderSuccessor(node4, node5);System.out.println(result);}public static TreeNode inorderSuccessor(TreeNode root, TreeNode p) {StackTreeNode stack new Stack();TreeNode cur root;boolean found false;while (cur ! null || !stack.isEmpty()) {while (cur ! null) {stack.push(cur);cur cur.left;}cur stack.pop();if (found) {break;}else if (p cur) {found true;}cur cur.right;}return cur;}
}分析 时间复杂度Oh的解法
下面按照在二叉搜索树中根据节点的值查找节点的思路来分析。从根节点开始每到达一个节点就比较根节点的值和节点p的值。如果当前节点的值小于或等于节点p的值那么节点p的下一个节点应该在它的右子树。如果当前节点的值大于节点p的值那么当前节点有可能是它的下一个节点。此时当前节点的值比节点p的值大但节点p的下一个节点是所有比它大的节点中值最小的一个因此接下来前往当前节点的左子树确定是否能找到值更小但仍然大于节点p的值的节点。重复这样的比较直至找到最后一个大于节点p的值的节点就是节点p的下一个节点。
解时间复杂度Oh的解法
public class Test {public static void main(String[] args) {TreeNode node1 new TreeNode(1);TreeNode node2 new TreeNode(2);TreeNode node3 new TreeNode(3);TreeNode node4 new TreeNode(4);TreeNode node5 new TreeNode(5);TreeNode node6 new TreeNode(6);node4.left node2;node4.right node5;node2.left node1;node2.right node3;node5.right node6;TreeNode result inorderSuccessor(node4, node5);System.out.println(result);}public static TreeNode inorderSuccessor(TreeNode root, TreeNode p) {TreeNode cur root;TreeNode result null;while (cur ! null) {if (cur.val p.val) {result cur;cur cur.left;}else {cur cur.right;}}return result;}
}
