# Tree [Python]

## 建構子
> Tree大部分都是採用linked list的解法

class TreeNode():
    def __init__(self,val,left=None,right=None):
        self.val = val
        self.left = left
        self.right = right

## 尋訪走法 Traversal
### 1. PreOrder

def pretraverse(root):
    if root!= None:
        print(root.val)
        pretraverse(root.left)
        pretraverse(root.right)

### 2. InOrder

def intraverse(root):
    if root!= None:
        pretraverse(root.left)
        print(root.val)
        pretraverse(root.right)

### 3. PostOrder

def posttraverse(root):
    if root!= None:
        pretraverse(root.left)
        pretraverse(root.right)
        print(root.val)

### 4. LevelOrder
:bulb:一定要用Queue處理，先把root pop出去，再把左子樹和右子樹放到queue裡

import queue
def leveltraverse(root):
    q = queue.Queue()
    q.put(root)
    while not q.empty():
        a = q.get()
        print(a.val)
        if root != None:
            q.put(root.left)
            q.put(root.right)

## 樹的種類 Tree
### 1. Binary Tree (BT)
每個root都會有left child和right child
大部分的問題都是用遞迴解決
* 計算node總數(左子樹的node+右子樹的node+1)

def countNode(root):
    if root == None:
        return 0
    else:
        left_count = countNode(root.left)
        right_count = countNode(root.right)
    return left_count+right_count+1

* 計算tree高度(1+Max(左子樹的高度,右子樹的高度)
> Max Depth

def max_depth(root):
    if root == None:
        return 0
    else:
        left_height = max_depth(root.left)
        right_height = max_depth(root.right)
    return 1+max(left_height, right_height)

> min depth

def min_depth(root):
    if root == None:
        return 0
    elif not root.left and root.right:
        return 1+min_depth(root.right)
    elif root.left and not root.right:
        return 1+min_depth(root.left)
    elif root.left and root.right:
        return 1+min(min_depth(root.left), min_depth(root.right)
    return 1

* 計算leaf總數(左子樹的leaf+右子樹的leaf)

def countLeaf(root):
    if root == None:
        return 0
    else:
        left_count = countLeaf(root.left)
        right_count = countLeaf(root.right)
        if (left_count+right_count) == 0:
            return 1
        else:
            return left_count+right_count

* 判斷BT是否相等(左子樹是否相同，右邊子樹是否相同)

def equal(root1, root2):
    flag = false
    if (root1 == None) and (root2 == None):
        return true
    else if (root1!= None) and (root2 != None):
        if root1.val == root2.val:
            if equal(root1.left, root2.left):
                flag = equal(root1.right, root2.right)
        return flag
    else:
        return false

### 2. Binary Search Tree (BST)
:bulb:root的val有大小順序之分，root.left < root < root.right

def BSTinsert(root, val):
    if root == None:
        root = TreeNode(val=val)
        return root
        else:
            if (val < root.val):
                root.left = BSTinsert(root.left,val)
            else:
                root.right = BSTinsert(root.right,val)
        return root

### 3. AVL Tree
任一左右子樹高度不能相差超過1
* 確認是否為平衡樹(每一個node都要回傳樹的高度再相減)

def isBalanced(root):
    if root == None:
        return 0
    if (root.left == None) and (root.right == Noen):
        return 1
    left_h = isBalanced(root.left)
    right_h = isBalanced(root.right)
    if abs(left_h - right_h) >=2:
        self.balance = False
    return 1+max(left_h, right_h)
def chek(root):
    self.balance = True
    self.isBalanced(root)
    return self.balance

### 常見應用題
* 計算root to leaf的路徑總和

def PathSum(root, targetSum):
    if root == None:
        return False
    newtarget = targetSum - root.val
    if newtarget == 0 and root.left == None and root.right == None:
        return True
    if self.targetSum(root.left, targetSum):
        return True
    if self.targetSum(root.right, targetSum):
        return True
    return False

<br>

###### tags: `Python`