国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

[Leetcode] Count Complete Tree Nodes 統計完全樹節點數

animabear / 2306人閱讀

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

Count Complete Tree Nodes

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.

遞歸樹高法 復雜度

時間 O(N) 空間 O(1)

思路

完全二叉樹的一個性質是,如果左子樹最左邊的深度,等于右子樹最右邊的深度,說明這個二叉樹是滿的,即最后一層也是滿的,則以該節點為根的樹其節點一共有2^h-1個。如果不等于,則是左子樹的節點數,加上右子樹的節點數,加上自身這一個。

注意

這里在左節點遞歸時代入了上次計算的左子樹最左深度減1,右節點遞歸的時候代入了上次計算的右子樹最右深度減1,可以避免重復計算這些深度

做2的冪時不要用Math.pow,這樣會超時。用1<

代碼
public class Solution {
    public int countNodes(TreeNode root) {
        return countNodes(root, -1, -1);
    }
    
    private int countNodes(TreeNode root, int lheight, int rheight){
        // 如果沒有上輪計算好的左子樹深度,計算其深度
        if(lheight == -1){
            lheight = 0;
            TreeNode curr = root;
            while(curr != null){
                lheight++;
                curr = curr.left;
            }
        }
        // 如果沒有上輪計算好的右子樹深度,計算其深度
        if(rheight == -1){
            rheight = 0;
            TreeNode curr = root;
            while(curr != null){
                rheight++;
                curr = curr.right;
            }
        }
        // 如果兩個深度一樣,返回2^h-1
        if(lheight == rheight) return (1 << lheight) - 1;
        // 否則返回左子樹右子樹節點和加1
        return 1 + countNodes(root.left, lheight - 1, -1) + countNodes(root.right, -1, rheight - 1);
    }
}
迭代樹高法 復雜度

時間 O(N) 空間 O(1)

思路

用迭代法的思路稍微有點不同,因為不再是遞歸中那樣的分治法,我們迭代只有一條正確的前進方向。所以,我們判斷的時左節點的最左邊的深度,和右節點的最左邊深度。因為最后一層結束的地方肯定在靠左的那側,所以我們要找的就是這個結束點。如果兩個深度相同,說明左子樹和右子樹都是滿,結束點在右側,如果右子樹算出的最左深度要小一點,說明結束點在左邊,右邊已經是殘缺的了。根據這個大小關系,我們可以確定每一層的走向,最后找到結束點。另外,還要累加每一層的節點數,最后如果找到結束點,如果結束點是左節點,就多加1個,如果結束點是右節點,就多加2個。

注意

同樣的,記錄上次計算的最左深度,可以減少一些重復計算

用int記錄上次最左深度更快,用Integer則會超時

代碼

未優化版本

public class Solution {
    public int countNodes(TreeNode root) {
        int res = 0;
        Integer lheight = null, rheight = null;
        while(root != null){
            // 得到左節點的最左深度
            int leftH = getH(root.left);
            // 得到右節點的最左深度
            int rightH = getH(root.right);
            // 左節點的最左深度大,說明右邊已經殘缺,結束點在左邊
            if(leftH > rightH){
                if(rightH != 0) res += 1 << rightH;
                else return res + 2;
                root = root.left;
            // 否則說明結束點在右邊
            } else {
                if(leftH != 0) res += 1 << leftH;
                else return res + 1;
                root = root.right;
            }
        }
        return res;
    }
    
    private int getH(TreeNode root){
        int h = 0;
        while(root != null){
            ++h;
            root = root.left;
        }
        return h;
    }
}

public class Solution {
    public int countNodes(TreeNode root) {
        int res = 0;
        int lheight = -1, rheight = -1;
        while(root != null){
            // 如果沒有上次記錄的左邊最左深度,重新計算
            if(lheight == -1){
                TreeNode curr = root.left;
                lheight = 0;
                while(curr != null){
                    curr = curr.left;
                    lheight++;
                }    
            }
            // 如果沒有上次記錄的右邊最左深度,重新計算
            if(rheight == -1){
                TreeNode curr = root.right;
                rheight = 0;
                while(curr != null){
                    curr = curr.left;
                    rheight++;
                }
            }
            // 深度相同,說明結束點在右邊
            if(lheight == rheight){
                // 如果是不是最后一個節點,累加這一層的節點
                if(lheight != 0){
                    res += 1 << lheight;
                } else {
                // 如果是最后一個節點,結束點在右邊意味著右節點是缺失的,返回res+1
                    return res + 1;
                }
                root = root.right;
                lheight = rheight - 1;
                rheight = -1;
            // 否則結束點在左邊
            } else {
                // 如果是不是最后一個節點,累加這一層的節點
                if(rheight != 0){
                    res += 1 << rheight;
                } else{
                // 如果是最后一個節點,返回res+2
                    return res + 2;
                }
                root = root.left;
                lheight = lheight - 1;
                rheight = -1;
            }
        }
        return res;
    }
}

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

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

相關文章

  • leetcode222. Count Complete Tree Nodes

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

    crossoverJie 評論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 評論0 收藏0
  • 315. Count of Smaller Numbers After Self

    摘要:題目鏈接的題,用來做,這種求有多少的題一般都是。里多加一個信息表示以為的節點數。也可以做,因為是統計有多少的,其實就是求從最小值到的。的是,要做一個映射,把的值映射到之間。所以先把給一下,用一個來做映射。還有的方法,參考 315. Count of Smaller Numbers After Self 題目鏈接:https://leetcode.com/problems... divi...

    cnio 評論0 收藏0
  • leetcode331. Verify Preorder Serialization of a Bi

    摘要:如果我們從右往左看先序遍歷,就知道后兩個節點如果遇到第三個節點,則該節點就應當是這兩個節點的父節點。如果在遍歷的過程中根節點數量小于,則說明這棵樹有問題。而如果遍歷結束之后,剩下的根節點數不等于,也說明這個先序遍歷存在問題。 題目要求 One way to serialize a binary tree is to use pre-order traversal. When we en...

    weapon 評論0 收藏0

發表評論

0條評論

animabear

|高級講師

TA的文章

閱讀更多
最新活動
閱讀需要支付1元查看
<