[LeetCode] 222. Count Complete Tree Nodes

kamushin233 發(fā)布于2019-08-16 13:54 / 1306人閱讀

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 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.

Example:

Input: 
    1
   / 
  2   3
 /   /
4  5 6

Output: 6

Solution

class Solution {
    public int countNodes(TreeNode root) {
        if (root == null) return 0;
        int height = 0;
        TreeNode left = root.left, right = root.right;
        while (left != null && right != null) {
            height++;
            left = left.left;
            right = right.right;
        }
        if (left == null && right == null) return (1 << (height+1)) - 1;
        else return 1 + countNodes(root.left) + countNodes(root.right);
    }
}

GPU云服務(wù)器云服務(wù)器 Nodes complete 222cc cc222

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/72536.html

相關(guān)文章

leetcode222. Count Complete Tree Nodes

摘要：題目要求計算一個完全二叉樹的節(jié)點個數(shù)。其中完全二叉樹是指除了最后一行，其余的每一行都必須是滿節(jié)點的樹。當(dāng)然超時啦思路二講道理的遞歸思路一很明顯沒有充分利用這是一顆完全二叉樹的條件。題目要求 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
222. Count Complete Tree Nodes

摘要：題目解答學(xué)了的方法哈哈這里是從開始算起，所以求出來的結(jié)果是實際是這一步很巧妙，把根結(jié)點加上，然后分治左結(jié)點和右結(jié)點，如果是葉子結(jié)點，在中就返回題目：Given a complete binary tree, count the number of nodes. Definition of a complete binary tree from Wikipedia:In a compl...

callmewhy 2019-08-14 14:14 評論0 收藏0
[Leetcode] Count Complete Tree Nodes 統(tǒng)計完全樹節(jié)點數(shù)

摘要：如果不等于，則是左子樹的節(jié)點數(shù)，加上右子樹的節(jié)點數(shù)，加上自身這一個。注意這里在左節(jié)點遞歸時代入了上次計算的左子樹最左深度減，右節(jié)點遞歸的時候代入了上次計算的右子樹最右深度減，可以避免重復(fù)計算這些深度做的冪時不要用，這樣會超時。 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-Tree] Path Sum I II III

摘要：解題思路利用遞歸，對于每個根節(jié)點，只要左子樹和右子樹中有一個滿足，就返回每次訪問一個節(jié)點，就將該節(jié)點的作為新的進行下一層的判斷。代碼解題思路本題的不同點是可以不從開始，不到結(jié)束。代碼當(dāng)前節(jié)點開始當(dāng)前節(jié)點左節(jié)點開始當(dāng)前節(jié)點右節(jié)點開始 Path SumGiven a binary tree and a sum, determine if the tree has a root-to-lea...

notebin 2019-08-16 10:26 評論0 收藏0