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
      }