2021-07-11：给定一个棵完全二叉树，返回这棵树的节点个数，要求时间复杂度小于O(树的节点数)。

福大大架构师每日一题

发布于 2021-08-05 16:22:46

2540

发布于 2021-08-05 16:22:46

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

2021-07-11：给定一个棵完全二叉树，返回这棵树的节点个数，要求时间复杂度小于O(树的节点数)。

福大大答案2021-07-11：

右树最左节点层数==左树最左节点层数，左树是满二叉树，统计左树节点个数，递归右树。

右树最左节点层数!=左树最左节点层数，右树是满二叉树，统计右树节点个数，递归左树。

时间复杂度：O(logN的平方)。空间复杂度：O(logN)。

代码用golang编写。代码如下：

package main

import "fmt"

func main() {
    head := &Node{}
    head.Left = &Node{}
    head.Right = &Node{}
    head.Left.Left = &Node{}
    head.Left.Right = &Node{}
    head.Right.Left = &Node{}
    ret := nodeNum(head)
    fmt.Println(ret)
}

type Node struct {
    Val   int
    Left  *Node
    Right *Node
}

// 请保证head为头的树，是完全二叉树
func nodeNum(head *Node) int {
    if head == nil {
        return 0
    }
    return bs(head, 1, mostLeftLevel(head, 1))
}

// 当前来到node节点，node节点在level层，总层数是h
// 返回node为头的子树(必是完全二叉树)，有多少个节点
func bs(node *Node, Level int, h int) int {
    if Level == h {
        return 1
    }
    if mostLeftLevel(node.Right, Level+1) == h {
        return (1 << (h - Level)) + bs(node.Right, Level+1, h)
    } else {
        return (1 << (h - Level - 1)) + bs(node.Left, Level+1, h)
    }
}

// 如果node在第level层，
// 求以node为头的子树，最大深度是多少
// node为头的子树，一定是完全二叉树
func mostLeftLevel(node *Node, level int) int {
    for node != nil {
        level++
        node = node.Left
    }
    return level - 1
}

执行结果如下：