LeetCode222. 完全二叉树的节点个数-Java&Go-DFS | BFS

• 算法
  • 1.DFS-递归
  • 2.递归
    • 根节点为null时，共有0个节点
    • 根节点不为null时，节点个数等于根节点+左子树节点个数+右子树节点个数
  • 3.优化
    • 当最左子节点和最右子节点深度相同时，这是一个满二叉树，节点个数可以直接计算为2^深度 - 1

public int countNodes(TreeNode root) {
    if (root == null) {
        return 0;
    }
    return 1 + countNodes(root.left) + countNodes(root.right);
}

public int countNodes(TreeNode root) {
    if (root == null) {
        return 0;
    }

    int level = 0;
    TreeNode l = root, r = root;
    while (l != null && r != null) {
        level++;
        l = l.left;
        r = r.right;
    }

    if (l == null && r == null) {
        return (1 << level) - 1;
    } else {
        return 1 + countNodes(root.left) + countNodes(root.right);
    }
}

func countNodes(root *TreeNode) int {
    if root == nil {
        return 0
    }
    return 1 + countNodes(root.Left) + countNodes(root.Right)
}

func countNodes(root *TreeNode) int {
    if root == nil {
        return 0
    }

    level := 0
    l, r := root, root
    for l != nil && r != nil {
        level++
        l, r = l.Left, r.Right
    }

    if l == nil && r == nil {
        return (1 << level) - 1
    } else {
        return 1 + countNodes(root.Left) + countNodes(root.Right)
    }
}

• 算法
  • 1.BFS-层次遍历
  • 2.队列进行层次遍历

public int countNodes(TreeNode root) {
    if (root == null) {
        return 0;
    }

    int sum = 0;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        int size = queue.size();
        sum += size;
        while (size-- > 0) {
            TreeNode curr = queue.poll();
            if (curr.left != null) {
                queue.offer(curr.left);
            }
            if (curr.right != null) {
                queue.offer(curr.right);
            }
        }
    }
    return sum;
}

func countNodes(root *TreeNode) int {
    if root == nil {
        return 0
    }

    sum, queue := 0, list.New()
    queue.PushBack(root)
    for queue.Len() > 0 {
        size := queue.Len()
        sum += size
        for size > 0 {
            curr := queue.Remove(queue.Front()).(*TreeNode)
            if curr.Left != nil {
                queue.PushBack(curr.Left)
            }
            if curr.Right != nil {
                queue.PushBack(curr.Right)
            }
            size--
        }
    }
    return sum
}