# Binary Tree

###### tags: `LeetCode筆記`

- 了解樹及二元樹的觀念
- 熟悉各種Traversal的方式
- 利用Recursion解決問題

## :memo: 一、Traversal

### 1. Preorder Traversal (DLR)
### 2. Inorder Traversal (LDR)
Binary Search Tree可以利用Inorder Traversal去由小到大排序

### 3. Postorder Traversal (LRD)
mathematical expression:
4\*(7-2)+5

### 4. Level Order Traversal
這個方式的coding較難，有利用recursion及iteration(BFS)兩種方法，要再去記憶此coding
**時間: O(N)**
**空間: O(N)**

## :memo: *Binary Tree Preorder Traversal (Easy)
Given the root of a binary tree, return the **preorder** traversal of its nodes' values.



### 作法 recursion
在副程式的parameter的vector要加&

class Solution {
public:
    void DLR_traverse(TreeNode* root, vector<int>& res) {
        if (root == nullptr) {
            return;
        }
        
        res.push_back(root->val);
        
        if (root->left != nullptr) {
            DLR_traverse(root->left, res);
        }
        
        if (root->right != nullptr) {
            DLR_traverse(root->right, res);
        }
        
        return;
    }
    
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        DLR_traverse(root, res);
        
        return res;
    }
};

### 作法 iteration (not easy)

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> answer;
        stack<TreeNode*> iStack;
        iStack.push(root);
        
        // Note that we add currNode's right child to the stack first.
        while (!iStack.empty()) {
            TreeNode* currNode = iStack.top();
            iStack.pop();
            if (currNode != nullptr) {
                answer.push_back(currNode -> val);
                iStack.push(currNode -> right);
                iStack.push(currNode -> left);
            }
        }
        
        return answer;
    }
};

## :memo: *Binary Tree Inorder Traversal (Easy)
Given the root of a binary tree, return the **inorder** traversal of its nodes' values.



### 作法 recursion

class Solution {
public:
    void LDR_traverse(TreeNode* root, vector<int>& res) {
        if (root == nullptr) {
            return;
        }
        
        if (root->left != nullptr) {
            LDR_traverse(root->left, res);
        }
        
        res.push_back(root->val);
        
        if (root->right != nullptr) {
            LDR_traverse(root->right, res);
        }
    }
    
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        
        LDR_traverse(root, res);
        
        return res;
    }
};

### 作法 iteration (not easy)

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> s;
        TreeNode* curr = root;
        while (curr != nullptr || !s.empty()) {
            while (curr != nullptr) {
                s.push(curr);
                curr = curr->left;
            }
            curr = s.top();
            s.pop();
            res.push_back(curr->val);
            curr = curr->right;
        }
        
        return res;
    }
};

## :memo: *Binary Tree Postorder Traversal (Easy)
Given the root of a binary tree, return the **postorder** traversal of its nodes' values.



### 作法 recursion

class Solution {
public:
    void LRD_traverse(TreeNode* root, vector<int>& res) {
        if (root == nullptr) {
            return;
        }
        
        if (root->left != nullptr) {
            LRD_traverse(root->left, res);
        }
        
        if (root->right != nullptr) {
            LRD_traverse(root->right, res);
        }
        
        res.push_back(root->val);
    }
    
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;
        
        LRD_traverse(root, res);
        
        return res;
    }
};

### 作法 iteration (not easy)

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        if (root == nullptr) {
            return {};
        }
        vector<int> ans;
        stack<TreeNode*> s;
        s.push(root);
        
        while (!s.empty()) {
            TreeNode* curr = s.top();
            if (curr->left) {
                s.push(curr->left);
                curr->left = nullptr;
            }
            else {
                if (curr->right) {
                    s.push(curr->right);
                    curr->right = nullptr;
                }
                else {
                    ans.push_back(curr->val);
                    s.pop();
                }
            }
        }
        
        return ans;
    }
};

## :memo: *Binary Tree Level Order Traversal (Medium)
Given the root of a binary tree, return the **level order** traversal of its nodes' values. (i.e., from left to right, level by level).



### 作法 recursion C
depth是有幾列(層)全域變數，level是用來遞迴的區域變數，用來將同層level的節點放進同depth列

Recursion Version:

int depth;
void counter(struct TreeNode* root, int size) {
    if (root == NULL)
    {
        return;
    }
    
    if (size > depth)
    {
        depth = size;  //count the depth
    }       
    
    counter(root->left, size + 1);
    counter(root->right, size + 1);    
}


void travel(struct TreeNode* root, int** returnColumnSizes, int level, int** result){
    if (root == NULL)
    {
        return;
    }
    
    result[level][(*returnColumnSizes)[level]++] = root->val;  //store the value to target level
    travel(root->left, returnColumnSizes, level + 1, result);
    travel(root->right, returnColumnSizes, level + 1, result);
}


int** levelOrder(struct TreeNode* root, int* returnSize, int** returnColumnSizes){
    //initialization
    depth = 0;
    counter(root, 0);
    depth++;
    
    int** result = (int**) malloc(sizeof(int*) * depth);    
    for (int i = 0; i < depth; i++)
    {
        result[i] = (int*) malloc(sizeof(int) * 256);
    }
        
    *returnColumnSizes = (int*) calloc(depth, sizeof(int));
    
    if (root == NULL) 
    {
        *returnSize = 0;
        return result;
    }
    
    travel(root, returnColumnSizes, 0, result);
    *returnSize = depth;
    
    return result;
}

### 作法 iteration C++
經典用BFS去解

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> ans;
        queue<TreeNode*> q;
        
        if (root) {
            q.push(root);    
        }       
        
        TreeNode* curr;
        while (!q.empty()) {
            int size = q.size();
            ans.push_back(vector<int>());
            for (int i = 0; i < size; ++i) {        // traverse nodes in the same level
                curr = q.front();
                q.pop();
                ans.back().push_back(curr->val);     // visit the root
                if (curr->left) {
                    q.push(curr->left);             // push left child to queue if it is not null
                }
                if (curr->right) {
                    q.push(curr->right);            // push right child to queue if it is not null
                }
            }
        }

        return  ans;
    }
};

## :memo: *Maximum Depth of Binary Tree (Easy)


### 作法

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (root == nullptr) {
            return 0;
        }
        
        return max(maxDepth(root->left) + 1, maxDepth(root->right) + 1);
    }
};

## :memo: Symmetric Tree (Easy)


### 作法 array記錄 浪費空間
寫兩個function(LRD,RLD)去traverse並記錄順序，再比較是否完全相同

### 作法 recursion
參數就帶left和right一個LRD,一個RLD去遞迴，判斷式一定寫!=就false,不可以寫等於就true!!!!(還不知道為什麼)

class Solution {
public:
    bool check_left_right_subtree_is_symmetric(TreeNode* sub_left, TreeNode* sub_right) {
        if (sub_left == nullptr && sub_right != nullptr) {
            return false;
        }
        if (sub_left != nullptr && sub_right == nullptr) {
            return false;
        }
        if (sub_left == nullptr && sub_right == nullptr) {
            return true;
        }        

        bool res = false;        
        res = check_left_right_subtree_is_symmetric(sub_left->left, sub_right->right);
        if (res == false) {
            return false;
        }
        
        res = check_left_right_subtree_is_symmetric(sub_left->right, sub_right->left);          
        if (sub_left->val != sub_right->val) {      //  一定寫!=就false,不可以寫等於就true!!!!
            return false;
        }
        
        return res;
    }
    
    bool isSymmetric(TreeNode* root) {
        if (root->left == nullptr && root->right == nullptr) {
            return true;
        }
        if (root->left != nullptr && root->right != nullptr) {
            return check_left_right_subtree_is_symmetric(root->left, root->right);
        }
        
        return false;
    }
};

### 作法 iteration

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        queue<TreeNode*> q;
        
        q.push(root);
        q.push(root);
        while (!q.empty()) {
            TreeNode* t1 = q.front();
            q.pop();
            TreeNode* t2 = q.front();
            q.pop();
            if (t1 == nullptr and t2 == nullptr) {
                continue;
            }
            if (t1 == nullptr or t2 == nullptr) {
                return false;
            }
            if (t1->val != t2->val) {
                return false;
            }
            q.push(t1->left);
            q.push(t2->right);
            q.push(t1->right);
            q.push(t2->left);
        }

        return true;
    }
};

## :memo: Path Sum (Easy)


### 作法 stupid
base case : 走到葉節點，此時要記錄的路線+1

function一開始先加上經過的節點數值，之後去左子樹遞迴後再去右子樹遞迴，**從右子樹遞迴回來後要減掉剛才加的此節點的數值**，function結束，會記錄所有路線的sum

### 作法 recursion C++
每往下就加起來(不用存，用參數傳就好)，到葉節點在檢查相不相等，true的話就一路回傳true

class Solution {
public:
    bool checkTargetSum(TreeNode* root, int sum, int targetSum) {
        if (root->left == nullptr && root->right == nullptr) {
            if (root->val + sum == targetSum) {
                return true;
            }
        }
        else {
            sum += root->val;
        }
        
        bool res = false;
        if (root->left != nullptr) {
            res = checkTargetSum(root->left, sum, targetSum);
        }
        if (res == true) {
            return true;
        }
        if (root->right != nullptr) {
            res = checkTargetSum(root->right, sum, targetSum);
        }
        if (res == true) {
            return true;
        }
        
        return false;
    }
    
    bool hasPathSum(TreeNode* root, int targetSum) {
        if (root == nullptr) {
            return false;
        }
        
        return checkTargetSum(root, 0, targetSum);
    }
};

## :memo: Count Univalue Subtrees (Medium)


### 作法
遞迴子樹是否符合值一樣同時符合再在這個節點與子節點值是否一樣同時用一變數is_unival代表現在這個節點的左子樹右子樹都為值一樣的子樹

bool traverse(struct TreeNode* root, int* count){
    if (root == NULL)
    {
        return true;
    }
    
    bool is_unival = true;
    
    if (root->left != NULL)
    {
        is_unival = traverse(root->left, count) && is_unival && root->left->val == root->val;
    }
    
    if (root->right != NULL)
    {
        is_unival = traverse(root->right, count) && is_unival && root->right->val == root->val;
    }
    
    if (!is_unival)
    {
        return false;
    }
    
    (*count)++;
    
    return true;
}

int countUnivalSubtrees(struct TreeNode* root){
    if (root == NULL)
    {
        return 0;
    }
    int count = 0;
    
    traverse(root, &count);
    
    return count;
}

### 作法 C++

class Solution {
public:
    int count = 0;
    
    bool is_uni(TreeNode* root) {
        if (root->left == nullptr && root->right == nullptr) {
            count++;
            
            return true;
        }
        
        bool is_unival = true;
        
        if (root->left != nullptr) {
            is_unival = is_uni(root->left) && is_unival && root->left->val == root->val;
        }        
        if (root->right != nullptr) {
            is_unival = is_uni(root->right) && is_unival && root->right->val == root->val;
        }
        
        if (!is_unival) {
            return false;
        }
        count++;
        
        return true;
    } 
    int countUnivalSubtrees(TreeNode* root) {
        if (root ==nullptr) {
            return 0;
        }
        
        is_uni(root);
        
        return count;
    }
};

## :memo: *Construct Binary Tree (Medium)

### 作法 C
#### 1. from Inorder and Postorder


利用mid去分成左半部右半部，當前curr的數值等於postorder的最尾巴數值，mid是inorder的curr數值的位置，找到後進行先往左子樹遞迴再往右子樹遞迴，function結束
關鍵在如何填參數數字:
**buildTree(&inorder[0],mid,&postorder[0],mid);**
**buildTree(&inorder[mid+1],inorderSize-mid-1,&postorder[mid],inorderSize-mid-1);**

if (inorderSize == 0)
{
    return NULL;
}

struct TreeNode* curr = (struct TreeNode*) malloc(sizeof(struct TreeNode));
curr->val = postorder[postorderSize-1];

int mid = 0;
while (inorder[mid] != curr->val)
{
    ++mid;
}

curr->left = buildTree(&inorder[0], mid, &postorder[0],mid);
curr->right = buildTree(&inorder[mid + 1], inorderSize - mid - 1, &postorder[mid], inorderSize - mid - 1);

return curr;

#### 2. from Preorder and Inorder


利用mid去分成左半部右半部，當前curr的數值等於preorder的最前面數值，mid是inorder的curr數值的位置，找到後進行先往左子樹遞迴再往右子樹遞迴，function結束
關鍵在如何填參數數字: **buildTree(&preorder[1], mid, &inorder[0], mid);**
**buildTree(&preorder[mid + 1], inorderSize - mid - 1, &inorder[mid + 1],inorderSize - mid - 1);**

if (inorderSize == 0)
{
    return NULL;
}

struct TreeNode* curr = (struct TreeNode*) malloc(sizeof(struct TreeNode));
curr->val = preorder[0];

int mid = 0;
while (inorder[mid] != curr->val)
{
    ++mid;
}

curr->left = buildTree(&preorder[1], mid, &inorder[0], mid);
curr->right = buildTree(&preorder[mid + 1], inorderSize - mid - 1, &inorder[mid + 1],inorderSize - mid - 1);        

return curr;

### 作法 C++
兩個遞迴function順序不能更動，一個是先right再left，一個是先left再right，**coding呼叫遞迴順序是有意義的**

#### 1. from Inorder and Postorder

class Solution {
public:
    int postorderIndex;
    unordered_map<int, int> inorderIndexMap;
    
    TreeNode* rc(vector<int>& postorder, int left, int right){
        if (left > right) {
            return nullptr;
        }
        
        int rootValue = postorder[postorderIndex--];
        TreeNode* root = new TreeNode(rootValue);
        
        root->right = rc(postorder, inorderIndexMap[rootValue] + 1, right);
        root->left = rc(postorder, left, inorderIndexMap[rootValue] - 1);                
        
        return root;
    }
    
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        postorderIndex = postorder.size() - 1;
        
        for (int i = 0; i < inorder.size(); i++) {
            inorderIndexMap[inorder[i]] = i;    
        }
        
        return rc(postorder, 0, inorder.size() - 1);
    }
};

#### 2. from Preorder and Inorder

class Solution {
public:
    int preorderIndex;
    unordered_map<int, int> inorderIndexMap;
    
    TreeNode* rc(vector<int>& preorder, int left, int right) {
        if (left > right) {
            return nullptr;
        }
        
        int rootValue = preorder[preorderIndex++];
        TreeNode* root = new TreeNode(rootValue);
        
        root->left = rc(preorder, left, inorderIndexMap[rootValue] - 1);
        root->right = rc(preorder, inorderIndexMap[rootValue] + 1, right);
        
        return root;
    }
    
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        preorderIndex = 0;        
        
        for (int i = 0; i < inorder.size(); i++) {
            inorderIndexMap[inorder[i]] = i;
        }
        
        return rc(preorder, 0, preorder.size() - 1);
    }
};

## :memo: Populating Next Right Pointers in Each Node (Medium)


### 作法
因為這題是完美的二元樹，所以在作法上比較單純，先間左子節點的next指向右子節點後往左子樹遞迴，遞迴回來後將右子節點的next指向當前節點的next的左子節點，最後去往右子樹遞迴，function結束

if (root == NULL)
{
    return NULL;
}

if (root->left != NULL)
{
    root->left->next = root->right;
    traverse(root->left);
}

if (root->right != NULL && root->next != NULL)
{
    root->right->next = root->next->left;
}

if (root->right != NULL)
{
    traverse(root->right);
}

### 作法 level-travese C++
用level-travese去想，Queue資料結構加一行判斷式

class Solution {
public:
    Node* connect(Node* root) {
        if (root == nullptr) {
            return nullptr;
        }
        
        queue<Node*> q;
        root->next = nullptr;
        q.push(root);        
        while (!q.empty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                Node* curr = q.front();
                q.pop();
                if (q.size() != 0 && i < size - 1) {
                    curr->next = q.front();
                }                
                if (curr->left) {
                    q.push(curr->left);
                }
                if (curr->right) {
                    q.push(curr->right);
                }
            }
        }
        
        return root;
    }
};

## :memo: Populating Next Right Pointers in Each Node II (Medium)


### 作法
這題因為是不完美，所以要一直去找不為NULL的next，又有一個關鍵就是要**先往右子樹遞迴再往左子樹遞迴**

struct Node* get_next_leftmost(struct Node* node) {
    struct Node* next = node->next;
    while (next != NULL) 
    {
        if (next->left != NULL) 
        {
            return next->left;
        }
            
        if (next->right != NULL) 
        {
            return next->right;
        }           
        
        next = next->next;
    }
    
    return NULL;
}

struct Node* connect(struct Node* root) {
    if (root == NULL) 
    {
        return NULL;
    }           

    struct Node* next_leftmost = get_next_leftmost(root);
    if (root->left != NULL)
    {
        if (root->right != NULL)
        {
            root->left->next = root->right;
        }                
        else
        {
            root->left->next = next_leftmost;
        }                
    }

    if (root->right != NULL)
    {
        root->right->next = next_leftmost;
    }           

    connect(root->right);  //關鍵:先右再左
    connect(root->left);

    return root;
}

### 作法 level-traverse C++
用level-traverse跟上一題一模一樣的code= =，用level-travese去想，Queue資料結構加一行判斷式

class Solution {
public:
    Node* connect(Node* root) {
        if (root == nullptr) {
            return nullptr;
        }
        
        queue<Node*> q;
        q.push(root);
        while (!q.empty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                Node* curr = q.front();
                q.pop();
                if (q.size() > 0 && i < size - 1) {
                    curr->next = q.front();
                }
                if (curr->left) {
                    q.push(curr->left);
                }
                if (curr->right) {
                    q.push(curr->right);
                }
            }
        }
        
        return root;
    }
};

## :memo: *Lowest Common Ancestor of a Binary Tree (Medium)


### 作法 recursion C
這題範例僅僅4行就完成
原理是
1.
當前節點是p或q或NULL
就回傳當前節點
2.
如果左右都非NULL,則回傳root
如果左為NULL右非NULL,則回傳右
如果左非NULL右為NULL,則回傳左

struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) {
    if (!root || root == p || root == q) 
    {
        return root;
    }
    
    struct TreeNode* left = lowestCommonAncestor(root->left, p, q);
    struct TreeNode* right = lowestCommonAncestor(root->right, p, q);
    
    return !left ? right : !right ? left : root;
}

### 作法 iteration C++
第一個while把p,q的祖先用unordered_map去以child當index,parent當value的方式去串起來，接著利用unorder_set去insert節點p往上的所有parents，然後再從q節點往上看的parents之中重複出現在祖先的就是共同祖先

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        stack<TreeNode*> s;
        unordered_map<TreeNode*, TreeNode*> parent;
        
        parent[root] = nullptr;
        s.push(root);
        
        while (!parent.count(p) || !parent.count(q)) {
            TreeNode* node = s.top();
            s.pop();
            if (node->left != nullptr) {
                parent[node->left] = node;
                s.push(node->left);
            }
            if (node->right != nullptr) {
                parent[node->right] = node;
                s.push(node->right);
            }
        }
        
        unordered_set<TreeNode*> ancestors;
        
        while (p != nullptr) {
            ancestors.insert(p);
            p = parent[p];
        }
        
        while (!ancestors.count(q)) {
            q = parent[q];
        }
        
        return q;
    }
};

## :memo: Serialize and Deserialize Binary Tree (Hard)


### 作法
這題非常複雜，要將樹轉成序列後，再將序列轉成樹，共兩個function，要利用到字串處理及遞迴去完成，要花時間去將整個流程弄熟悉，幫助了解處理一項任務要經過多少程序，算是一件很完整的工作任務

## :memo: Binary Tree Longest Consecutive Sequence II (Medium)
Given the root of a binary tree, return the length of the longest consecutive path in the tree.

A consecutive path is a path where the values of the consecutive nodes in the path differ by one. This path can be either increasing or decreasing.

For example, [1,2,3,4] and [4,3,2,1] are both considered valid, but the path [1,2,4,3] is not valid.
On the other hand, the path can be in the child-Parent-child order, where not necessarily be parent-child order.


### 作法 Single traversal
回傳pair記錄遞增和遞減的長度是多少，回傳遞增和遞減分別在左子樹和右子樹最長長度

### trace圖:
**1.**
**2.**
**3.**
**4.**
**5.**
**6.**
**7.**
**8.**
**9.**
**10.**
**11.**
**12.**
**13.**
**14.**
**15.**
**16.**

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int maxval;

    pair<int, int> longestPath(TreeNode* root) {
        if (root == nullptr) {
            return {0, 0};
        }

        int inr = 1, dcr = 1;
        if (root->left != nullptr) {
            pair<int, int> left = longestPath(root->left);
            if (root->val == root->left->val + 1) {
                dcr = left.second + 1;
            } else if (root->val == root->left->val - 1) {
                inr = left.first + 1;
            }
        }
        if (root->right != nullptr) {
            pair<int, int> right = longestPath(root->right);
            if (root->val == root->right->val + 1) {
                dcr = max(dcr, right.second + 1);
            } else if (root->val == root->right->val - 1) {
                inr = max(inr, right.first + 1);
            }
        }

        maxval = max(maxval, dcr + inr - 1);

        return {inr, dcr};
    }

    int longestConsecutive(TreeNode* root) {
        maxval = 0;

        longestPath(root);

        return maxval;
    }
};

## :memo: 刷題檢討
這個章節有很重要的基礎資料結構的實作，基本定義及知識和如何在coding上完成Traversal，考試上手作的題目類型的coding，都在本章節上出現，從preorder and inorder或postorder and inorder建立一棵樹，這個coding要記熟!