222. Count Complete Tree Nodes

callmewhy 發布于2019-08-14 14:14 / 945人閱讀

摘要：題目解答學了的方法哈哈這里是從開始算起，所以求出來的結果是實際是這一步很巧妙，把根結點加上，然后分治左結點和右結點，如果是葉子結點，在中就返回

題目：
Given a complete binary tree, count the number of nodes.

Definition of a complete binary tree from Wikipedia:
In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.

解答：

public class Solution {
    //學了enum的方法哈哈
    public enum Direction {
        LEFT, RIGHT
    }
    
    public int getDepth(TreeNode root, Direction dir) {
        int depth = 0;
        //這里是從root開始算起，所以求出來的結果是實際depth + 1
        while (root != null) {
            depth++;
            if (dir == Direction.LEFT) {
                root = root.left;
            } else {
                root = root.right;
            }
        }
        return depth;
    }
    
    public int countNodes(TreeNode root) {
        if (root == null) return 0;
        int leftDepth = getDepth(root, Direction.LEFT);
        int rightDepth = getDepth(root, Direction.RIGHT);
        
        if (leftDepth == rightDepth) {
            //1 << leftDepth是2^(leftDepth)
            return (1 << leftDepth) - 1;
        } else {
            //這一步很巧妙，把根結點加上，然后分治左結點和右結點，如果是葉子結點，在countNodes中就返回1
            return 1 + countNodes(root.left) + countNodes(root.right);
        }
    }
}

云服務器 GPU云服務器 Nodes complete 222cc cc222

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/64885.html

leetcode222. Count Complete Tree Nodes

摘要：題目要求計算一個完全二叉樹的節點個數。其中完全二叉樹是指除了最后一行，其余的每一行都必須是滿節點的樹。當然超時啦思路二講道理的遞歸思路一很明顯沒有充分利用這是一顆完全二叉樹的條件。題目要求 Given a complete binary tree, count the number of nodes. Definition of a complete binary tree fro...

crossoverJie 2019-08-16 12:11 評論0 收藏0
[LeetCode] 222. Count Complete Tree Nodes

Problem Given a complete binary tree, count the number of nodes. Note: Definition of a complete binary tree from Wikipedia:In a complete binary tree every level, except possibly the last, is completel...

kamushin233 2019-08-16 13:54 評論0 收藏0
[Leetcode] Count Complete Tree Nodes 統計完全樹節點數

摘要：如果不等于，則是左子樹的節點數，加上右子樹的節點數，加上自身這一個。注意這里在左節點遞歸時代入了上次計算的左子樹最左深度減，右節點遞歸的時候代入了上次計算的右子樹最右深度減，可以避免重復計算這些深度做的冪時不要用，這樣會超時。 Count Complete Tree Nodes Given a complete binary tree, count the number of nod...

animabear 2019-08-14 12:41 評論0 收藏0
[LeetCode] 501. Find Mode in Binary Search Tree

Problem Given a binary search tree (BST) with duplicates, find all the mode(s) (the most frequently occurred element) in the given BST. Assume a BST is defined as follows: The left subtree of a node c...

NikoManiac 2019-08-16 13:51 評論0 收藏0
[LeetCode] Path Sum (I & II & III)

摘要： 112. Path Sum Problem Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum. Note: A leaf is a node...

張金寶 2019-08-19 11:09 評論0 收藏0