网站开发说明书模板,产品设计考研,烟台比较好的软件公司,常州市网站建设公司第一次见这个题#xff0c;看时间小于O(N)。。。。。
只能是二分啊。
但是怎么二分#xff0c;条件是什么#xff0c;真的想不到。 后来知道了#xff0c;我们要找最深一层最右边那个结点。借此确定结点个数。 我们知道#xff0c;满二叉树的结点个数和深度是有公式的看时间小于O(N)。。。。。
只能是二分啊。
但是怎么二分条件是什么真的想不到。 后来知道了我们要找最深一层最右边那个结点。借此确定结点个数。 我们知道满二叉树的结点个数和深度是有公式的那么我们找到最后一层最右边的结点其实就可以确定结点个数。 目标找箭头指向的结点。 我们采用二分法
1找到右子树的最左结点 如果右子树深度为34-1说明图中最后的1是存在的说明最后一行最右结点一定来自右子树否则 右子树深度为24-1不存在最后一行的结点。说明最后一行最右结点一定来自左子树. 判断之后如果是这种情况我们排除了左子树计算排除的结点个数如图并对右子树做相同的处理。 更新结点数未被框起的部分满二叉树公式11是根结点
对方框内重复此过程。 我们继续看右子树发现右子树深度为13-1.
说明最深层最右结点来自于左子树。所以对左子树重复上述过程 我们发现右子树深度12整棵树深度-1说明最深层最右结点来自于右子树所以对右子树重复此过程。
最终找到它 我们再回忆一下过程 1找到右子树最左节点确定了深度对右子树重复。 2找到右子树最左节点确定了深度对左子树重复。 3找到右子树最左节点确定了深度对右子树重复。 4找到 过程中可以
1把排除的部分全部加起来
2也可以记录每次的选择向左还是向右最终100010这种字符其实就是最后一层的结点个数。 贴上方法1的全部代码
public class Demo {public static class Node {public int value;public Node left;public Node right;public Node(int data) {this.value data;}}
//返回结点个数public static int nodeNum(Node head) {if (head null) {return 0;}return bs(head, 1, mostLeftLevel(head, 1));}
//返回根为node当前层数为l总深度为h的结点个数public static int bs(Node node, int l, int h) {if (l h) {return 1;}if (mostLeftLevel(node.right, l 1) h) { //右子树最深一行最左为空return (1 (h - l)) bs(node.right, l 1, h); //右bs左子树结点个数} else { //右子树最深一行最左不为空return (1 (h - l - 1)) bs(node.left, l 1, h);//左bs右子树结点个数}}
//计算树的高度public static int mostLeftLevel(Node node, int level) {while (node ! null) {level;node node.left;}return level - 1;}public static void main(String[] args) {Node head new Node(1);head.left new Node(2);head.right new Node(3);head.left.left new Node(4);head.left.right new Node(5);head.right.left new Node(6);System.out.println(nodeNum(head));}}
