222.完全二叉树的节点个数

【思路】

普通二叉树:层序遍历后统计item的个数,累加即可。

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

避免了不必要的节点遍历,节省了时间

  • 判断当前节点的子树是否为满二叉树:判断左右子树的深度是否相同,相同的话即满二叉树,用公式就可以算出满二叉树的节点了。

  • Java实现

    • 普通二叉树解法(层序遍历)
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    class Solution {
    public int countNodes(TreeNode root) {
    int num = 0;
    if(root == null)return num;
    Queue<TreeNode>queue = new LinkedList<TreeNode>();
    queue.add(root);
    while(!queue.isEmpty()){
    List<TreeNode>item = new ArrayList<>();
    int dep = queue.size();
    while(dep>0){
    TreeNode node = queue.poll();
    item.add(node);
    if(node.left!= null)queue.add(node.left);
    if(node.right != null)queue.add(node.right);
    dep--;
    }
    if(item.size() >0){
    num+=item.size();
    }
    }
    return num;
    }
    }
    • 完全二叉树解法:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    class Solution {
    public int countNodes(TreeNode root) {
    if(root == null)return 0;
    TreeNode nodeLeft = root.left;
    TreeNode nodeRight = root.right;
    int leftDepth=0,rightDepth = 0;
    while(nodeLeft!=null){
    nodeLeft = nodeLeft.left;
    leftDepth++;
    }
    while(nodeRight != null){
    nodeRight = nodeRight.right;
    rightDepth++;
    }
    //如果该二叉树是满二叉树
    if(leftDepth == rightDepth ){
    return (2 <<leftDepth)-1;
    }
    //否则就找到是满二叉树
    return countNodes(root.left)+countNodes(root.right) + 1;
    }
    }
  • Go实现

    • 普通二叉树解法(层序遍历):
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    func countNodes(root *TreeNode) int {
    num := 0
    if root == nil{
    return num
    }
    curLevel := []*TreeNode{root}
    for len(curLevel) >0 {
    nextLevel := []*TreeNode{}
    for _,node := range curLevel{
    if(node.Left != nil){
    nextLevel = append(nextLevel,node.Left)
    }
    if(node.Right != nil){
    nextLevel = append(nextLevel,node.Right)
    }
    }
    if(len(curLevel) > 0){
    num+=len(curLevel)
    }
    curLevel = nextLevel
    }
    return num
    }
    • 完全二叉树解法:

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      func countNodes(root *TreeNode) int {
      if root == nil{
      return 0
      }
      leftNode := root.Left
      rightNode := root.Right
      leftDepth,rightDepth := 0,0
      for leftNode != nil{
      leftDepth++
      leftNode = leftNode.Left
      }
      for rightNode != nil{
      rightDepth++
      rightNode = rightNode.Right
      }

      if leftDepth == rightDepth {
      return (2<<leftDepth) -1
      }

      return countNodes(root.Left) + countNodes(root.Right)+1
      }