kiniku
Binary Tree Problems（queue）（recursion）

Photo by Markus Winkler on Unsplash

Binary Tree Problems（queue）（recursion）

kiniku's photo
kiniku
·

2 min read

  1. Find the max key in a binary tree

    通常會先從最左邊開始尋找，並且比對左右子節點是否存在，又或是比較值的大小

    使用佇列方式跟level order使用queue的方式差不多，只是多了一個變數跟一個條件判斷，用來處理當二元樹裡的節點大於原本的節點時，就更新變數

    solution

  2. Count number of nodes in binary tree

    利用遞迴判斷是否存在左右子節點，如果存在就加1，並且再加1，並且回傳

    使用佇列方式是使用一個變數來代表size，在dequeue之前把變數加1，並且不斷的加入左右子節點，然後再dequeue把size加1，最後回傳

    solution

  3. Find the deepest node in binary tree

    隨著遞迴level也會跟著增加，在當左右子節點都不能加入時，就會回傳當前的level

    用佇列的話就是不斷地加入直到無法加入時就把該值回傳

    solution

  4. Count leaf nodes in binary tree

    當該節點的左右子節點都皆為NULL時，就回傳1代表樹葉節點

    加入佇列後判斷該節點的左右子節點是否為NULL，如果是就把變數加1

    solution

  5. Count full nodes in a Binary tree

    利用遞迴確定當該節點有左右子節點時，就回傳1，最後加總起來就是全部full nodes

    把節點加入到佇列後，一樣判斷是否擁有兩個子節點，如果有就加1

    solution

  6. Count half nodes in a Binary Tree

    跟判斷full nodes一樣，只是會改成當有其中一個子節點時，就回傳1

    當加入進佇列裡的節點，擁有一個子節點時，就把變數加1

    solution

  7. Sum of all nodes in a binary tree

    利用遞迴來回傳自己的值，以便後續增加

    使用佇列的話，就是不停地加入，然後在dequeue時，就把變數增加節點的值

    solution

  8. Find height of binary tree

    如果左子節點大於右子節點的話，就回傳左子節點並加1，因為包括自己

    solution

  9. Maximum Level Sum of a Binary Tree

    在加入一個節點後，也順便加入NULL節點，代表一個level的結束

  10. Find ancestors of given node in a Binary Tree

    透過遞迴來尋找傳入的值，如果找到的時候，就回傳1來印出祖先節點

    利用迴圈來推入節點，如果該節點就是要找的值，就會離開迴圈印出資料

    solution

  11. Lowest common ancestor in a binary tree

    solution

  12. Convert binary tree to mirror tree

    當找到左右子節點後，就把左右子節點交換

    solution
BinaryTrees