二分查找之完全二叉树的节点个数

LeetCode 222. 完全二叉树的节点个数

给出一个完全二叉树，求出该树的节点个数。

说明：
完全二叉树的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 $1到2^h$ 个节点。
示例:

输入: 
    1
   / \
  2   3
 / \  /
4  5 6

输出: 6

解法一：利用递归

class Solution:
    def countNodes(self, root: TreeNode) -> int:
		if not root:
            return 0
        return self.countNodes(root.left) + self.countNodes(root.right) + 1

时间复杂度：$\mathcal{O}(N)$。
空间复杂度：$\mathcal{O}(d)=\mathcal{O}(\log N)$，其中 d 指的是树的的高度，运行过程中堆栈所使用的空间。

解法二：利用bfs广度优先遍历，也即层次遍历

class Solution:
    def countNodes(self, root: TreeNode) -> int:
        self.count = 0

        self.bfs(root)
        return self.count

    def bfs(self, root):
        if not root:
            return 0
        stack = [root]
        while stack:
            size = len(stack)
            for i in range(size):
                node = stack.pop()
                self.count += 1
                if node.left:
                    stack.append(node.left)
                if node.right:
                    stack.append(node.right)
        

解法三：

分析：首先统计二叉树左右子树的层数，有以下两种情况：
left == right。这说明，左子树一定是满二叉树，因为节点已经填充到右子树了，左子树必定已经填满了。所以左子树的节点总数我们可以直接得到，是$2^{left-1}$，加上当前这个root节点，则正好是$2^{left}$。再对右子树进行递归统计。
left != right。说明此时最后一层不满，但倒数第二层已经满了，可以直接得到右子树的节点个数。同理，右子树节点+root节点，总数为$2^{right}$。再对左子树进行递归查找。

class Solution:
    def depth(self,node: TreeNode) -> int:
        d=0
        while node :
            node = node.left
            d+=1
        return d
    def countNodes(self, root: TreeNode) -> int:
        if not root:
            return 0
        lnode = self.depth(root.left)
        rnode = self.depth(root.right)
        if lnode==rnode:
            return 2**lnode+self.depth(root.right)
        else:
            return 2**rnode+self.depth(root.left)

变形：求完全二叉树的最后一层的最后一个节点

思路：类似于二分查找，
首先遍历最左分支，求出二叉树的高度；
然后对于每个子树的根节点，先从他的右子树开始，沿着左分支一直走到最后一层，
如果深度等于树的深度且该最后节点右边没有节点，则为所求,否则，右侧有节点，则遍历右子树；深度小于树的深度，则遍历左子树。
时间复杂度是O(logn)

def getlastnode(root):
	if not root:
		return None
	if not root.left and not roor.right:
		return root
	temp_node = root
	depth = 0
	while temp_node:　#计算二叉树的深度
		depth += 1
		temp_node = temp_node.left
	level = 0
	temp_depth = 0
	while root:
		level += 1 #当前遍历到哪一层，root为第一层
		if level == depth: # 防止右子树为空
			break
		curr = root
		if curr.right:　# 遍历右子树
			pcur = curr # 当前节点的父节点
			curr = curr.right
			temp_depth = level + 1
			while curr.left:　#一直往左走，计算右子树的深度
				temp_depth += 1
				pcur = curr
				curr = curr.left
			if temp_depth < depth:　# 右边深度小于树的深度，最后一个节点在左子树
				root = root.left　#二分查找左子树
			elif not pcur.right or pcur.right == curr:　#深度相等，且最后节点右侧没有节点
				return curr
			else:
				root = root.right　#深度相等，且最后节点右侧还有节点，二分查找右子树
		else:
			root = root.left　#没有右子树，查找左子树
	return root
		

更新一个解法，仿照二分查找法求完全二叉树的节点个数

• 依次求解二叉树左子树和左子树的高度
• 如果二者高度相等，那么最后一个节点肯定在右子树
• 如果左子树高度大于右子树高度，那么最后一个节点一定在左子树
• 终止条件为叶子节点
  这个地方容易迷，比如说，最后一层如果有两个叶子节点，那么一定是在第二个叶子节点终止，因为是递归求解深度，相等时，走的是右子树，所以保证了终止条件一定是最后一个叶子节点．

def depth(root):
    d = 0
    while root:
        d += 1
        root = root.left
    return d

def lastnode(root):
    if not root:
        return None
    if not root.left and not root.right:
        return root.val
    left_depth = depth(root.left)

    right_depth = depth(root.right)
    if left_depth == right_depth:
        return lastnode(root.right)
    else:
        return lastnode(root.left)