leetcode222. Count Complete Tree Nodes

crossoverJie 發布于2019-08-16 12:11 / 2578人閱讀

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

題目要求

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 int countNodes(TreeNode root) {
        if(root==null) return 0;
        return 1 + countNodes(root.left) + countNodes(root.right);
    }

思路二：講道理的遞歸

思路一很明顯沒有充分利用這是一顆完全二叉樹的條件。從另一個角度看，一顆完全二叉樹的左子樹和右子樹有兩種情況

左子樹比右子樹高

左子樹和右子樹一樣高

當左子樹和右子樹一樣高時，說明左子樹本身是一顆滿二叉樹，它的元素個數為2^h左-1。
當左子樹比右子樹高時，說明右子樹本身是一顆滿二叉樹，它的元素個數為2^h右-1(h為樹的高度)

所以每一次通過判斷左右子樹的高度可以得到其中一棵子樹的元素個數，這時再遞歸到另一顆子樹繼續計算直到當前元素為null。
代碼如下：

    int height(TreeNode root) {
        return root == null ? -1 : 1 + height(root.left);
    }
    public int countNodes2(TreeNode root) {
        int h = height(root);
        return h < 0 ? 0 :
               height(root.right) == h-1 ? (1 << h) + countNodes2(root.right)
                                         : (1 << h-1) + countNodes2(root.left);
    }

思路三：遞什么歸！

當遞歸轉化為循環且該循環并不需要使用棧這種數據結構時，性能往往會得到質的飛躍。在上面的思路二中采用遞歸，在這里我們將遞歸轉變為循環。同時我們只需要計算一次樹的高度，因為每一次選擇的子樹的高度都是上一個高度-1。

    int height2(TreeNode root){
        if(root==null) return -1;
        int height = 0;
        while(root.left!=null) {height++; root=root.left;}
        return height;
    }
    
    public int countNodes3(TreeNode root) {
        int count = 0;
        int height = height2(root);
        while(root!=null){
            if(height2(root.right)==height-1){
                count += 1<

想要了解更多開發技術，面試教程以及互聯網公司內推，歡迎關注我的微信公眾號！將會不定期的發放福利哦~

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

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

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

[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
222. Count Complete Tree Nodes

摘要：題目解答學了的方法哈哈這里是從開始算起，所以求出來的結果是實際是這一步很巧妙，把根結點加上，然后分治左結點和右結點，如果是葉子結點，在中就返回題目：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 統計完全樹節點數

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

摘要：解題思路利用遞歸，對于每個根節點，只要左子樹和右子樹中有一個滿足，就返回每次訪問一個節點，就將該節點的作為新的進行下一層的判斷。代碼解題思路本題的不同點是可以不從開始，不到結束。代碼當前節點開始當前節點左節點開始當前節點右節點開始 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