「力扣」第 222 题:求完全二叉树的节点数、满二叉树


「力扣」第 222 题:求完全二叉树的节点数、满二叉树

传送门:222. 完全二叉树的节点个数

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

说明:

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

示例:

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

输出: 6

分析:给定一棵完全二叉树,求完全二叉树的节点的个数。

  • 什么是完全二叉树?除了最后一层,所有层的节点数达到最大,与此同时,最后一层的所有节点集中在这一层的左侧。事实上,堆就是使用完全二叉树定义的。

  • 什么是满二叉树?所有层的节点数达到了最大。

Python 代码:

# Definition for a binary tree node.

# 222. 完全二叉树的节点个数
# 给出一个完全二叉树,求出该树的节点个数。
# 说明:完全二叉树的定义如下:
# 在完全二叉树中,除了最底层节点可能没填满外,
# 其余每层节点数都达到最大值,
# 并且最下面一层的节点都集中在该层最左边的若干位置。
# 若最底层为第 h 层,则该层包含 1~ 2h 个节点。
# 求完全二叉树的结点数、满二叉树。使用递归可以完成。


class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution:
    def countNodes(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        left_depth = self.__depth(root, True)
        right_depth = self.__depth(root, False)

        if left_depth == right_depth:
            # return 2 ** left_depth - 1
            return (1 << left_depth) - 1
        if left_depth > right_depth:
            return 1 + self.countNodes(root.left) + self.countNodes(root.right)

    def __depth(self, node, is_left):
        depth = 0
        while node:
            depth += 1
            node = node.left if is_left else node.right
        return depth

说明:体会在递归过程中,“减而治之”的策略。

LeetCode 第 222 题:求完全二叉树的结点数、满二叉树

Python 代码:

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution:
    def countNodes(self, root):
        left_depth = self.__depth(root, True)
        right_depth = self.__depth(root, False)

        if left_depth == right_depth:
            # return 2 ** left_depth - 1
            return (1 << left_depth) - 1
        if left_depth > right_depth:
            return 1 + self.countNodes(root.left) + self.countNodes(root.right)

    def __depth(self, node, is_left):
        depth = 0
        while node:
            depth += 1
            node = node.left if is_left else node.right
        return depth

LeetCode 第 222 题:给出一个完全二叉树,求出该树的节点个数(典型递归问题)

提示:如果是满二叉树,结点的个数是有规律可循的。那么是不是满二叉树,可以通过子树的深度来判断。

Python 代码:

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution:
    def countNodes(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        left_depth = self.__depth(root, True)
        right_depth = self.__depth(root, False)

        if left_depth == right_depth:
            # return 2 ** left_depth - 1
            return (1 << left_depth) - 1
        if left_depth > right_depth:
            return 1 + self.countNodes(root.left) + self.countNodes(root.right)

    def __depth(self, node, is_left):
        depth = 0
        while node:
            depth += 1
            node = node.left if is_left else node.right
        return depth


文章作者: liweiwei1419
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 liweiwei1419 !
评论
 上一篇
「力扣」第 230 题:二叉搜索树中第 K 小的元素 「力扣」第 230 题:二叉搜索树中第 K 小的元素
「力扣」第 230 题:二叉搜索树中第 K 小的元素 中文网址:230. 二叉搜索树中第K小的元素 ; 英文网址:230. Kth Smallest Element in a BST , 给定一个二叉搜索树,编写一个函数 kthSmal
下一篇 
「力扣」第 199 题:二叉树的右视图 「力扣」第 199 题:二叉树的右视图
「力扣」第 199 题:二叉树的右视图题解地址:DFS 和 BFS(Python 代码)。 说明:文本首发在力扣的题解版块,更新也会在第 1 时间在上面的网站中更新,这篇文章只是上面的文章的一个快照,您可以点击上面的链接看到其他网友对本文的
  目录