Leetcode刷題學習筆記 – 名詞解釋

Tree

最廣義的樹(Tree)對於樹上的node之child數目沒有限制，因此，每個node可以有多個child。
tree

Binary Tree

若限制node只能有兩個child，等價於「樹上的每一個node之degree皆為2」，此即稱為Binary Tree(二元樹)，並稱兩個child pointer為left child和right child。
BinaryTree

Full Binary Tree/Perfect Binary Tree

一棵Full Binary Tree(或稱作Perfect Binary Tree)具有以下性質：

  • 所有internal node都有兩個subtree(也就是兩個child pointer)；
  • 所有leaf node具有相同的level(或相同的height)。
  • 若一棵Full Binary Tree的leaf node之level為n，整棵樹共有2n−1個node。
    FullBinaryTree

Complete Binary Tree

若一棵樹的node按照Full Binary Tree的次序排列(由上至下，由左至右)，則稱此樹為Complete Binary Tree。
如下圖所示，樹共有10個node，且這十個node正好填滿Full Binary Tree的前十個位置，則此樹為Complete Binary Tree。
CompleteBinaryTree

tags: leetcode 刷題
Select a repo