一.题目

leetcode:222

完全二叉树节点个数
用层序遍历可以做,就是套模板,

层序遍历解法

func countNodes(root *TreeNode) int {
    if root==nil{
        return 0
    }
    lis := list.New()
    lis.PushBack(root)
    num := 1
    for lis.Len()>0{
        length := lis.Len()
        for i:=0;i<length;i++{
            node := lis.Remove(lis.Front()).(*TreeNode)
            if node.Left!=nil{
                lis.PushBack(node.Left)
                num++
            }
            if node.Right!=nil{
                lis.PushBack(node.Right)
                num++
            }

        }
    }
    return num
}

递归解法

func countNodes(root *TreeNode) int{
    var traversal func(node *TreeNode)
    num := 0
    traversal = func(node *TreeNode){
        if node==nil{
            return 
        }
        num++
        traversal(node.Left)
        traversal(node.Right)
    }
    traversal(root)
    return num
}

推荐:利用完全二叉树特性的递归解法

有一点不懂的是:为什么countNodes(root.Left)这个递归就可以返回左子树的个数,并没有返回任何值呀?

func countNodes(root *TreeNode) int {
    if root==nil{
        return 0
    }
    lefth, righth := 0,0
    left := root.Left
    right := root.Right
    for left!=nil{
        lefth++
        left = left.Left
    }
    for right!=nil{
        righth++
        right = right.Right
    }
    if righth==lefth{
        // 说明是完全二叉树,根据公式来,计算深度是优化
        return (2<<lefth)-1
    }
    // 不相等,不能优化
    return countNodes(root.Left) + countNodes(root.Right) + 1
}
分类: 算法

0 条评论

发表评论

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

ICP备案号: 辽ICP备20003309号