完全二叉树结点数

完全二叉树结点数_牛客题霸_牛客网

问题简述

给定一棵完全二叉树的头节点head，返回这棵树的节点个数。

思路：前序遍历

• 根据完全二叉树的性质，若当前节点的编号为 i，则左右子树的编号分别为 2*i 和 2*i+1；

• 统计出现过的最大编号即可；

Python

class Solution:
    def nodeNum(self , head: TreeNode) -> int:
        self.ret = 0
        
        def dfs(x, i):
            if not x: return 0
            
            self.ret = max(self.ret, i)
            l, r = dfs(x.left, i * 2), dfs(x.right, i * 2 + 1)
        
        dfs(head, 1)
        return self.ret