Leetcode 二叉树

LC222 完全二叉树的节点个数

这题主要是要完全理解完全二叉树。我们计算左子树和右子树高度，会出现两个情况

如果高度一样，左子树一定满了，在填右子树，左边确定了可以计算，右边不确定继续递归
如果高度不同，左子树一定没满，但是右子树一定满了，只是树高比左子树低1，右边确定了可以计算，左边不确定继续递归

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


func countNodes(root *TreeNode) int {
    if root == nil {
        return 0
    }
    
    leftDepth := getDepth(root.Left)
    rightDepth := getDepth(root.Right)
    
    if leftDepth == rightDepth {
        // 左子树是满二叉树，直接计算左子树节点数 + 根节点 + 递归右子树
        return (1 << leftDepth) + countNodes(root.Right)
    } else {
        // 右子树是满二叉树（但少一层），递归左子树
        return (1 << rightDepth) + countNodes(root.Left)
    }
}

func getDepth(node *TreeNode) int {
    depth := 0
    for node != nil {
        depth++
        node = node.Left
    }
    return depth
}