题目描述 已知一棵完全二叉树,求其节点的个数 要求:时间复杂度低于O(N),N为这棵树的节点个数 实现思路 若设二叉树的深度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 h 层所有的结点都连续集中在最左边,这就是完全二叉树。 首先判断根节点的右子树的左边界。 左子树的左边界在最后一层。 说明此时根的左子树为满二叉树 所有节点数 = 左子树 + 根节点 + 右子树 左子树为满二叉树,高度为lH=H-1。那么左子树的节点个数为(1 << lH) - 1也就是2的lH次方减一。 …

2020年4月2日 0条评论 11点热度 阅读全文

题目描述 判断一棵二叉树是否为二叉搜索树,完全二叉树 实现思路 public static class Node { int val; Node left; Node right; public Node(int data) { this.val = data; } } 二叉搜索树 二叉搜索树是一棵空树,或者是具有下列性质的二叉树: 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值; 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值; 它的左、右子树也分别为二叉排序树。 二叉搜索树在【中序遍…

2020年4月2日 0条评论 22点热度 阅读全文