今天透過三個LeetCode問題複習了二叉樹和二叉搜索樹，每個問題都包含多種解決方法。

94. Binary Tree Inorder Traversal

程度

Easy

題目

給定二元樹的 root ，傳回其節點值的中序遍歷。

想法

從根節點開始，先遍歷左子樹，然後訪問目前節點，最後遍歷右子樹。中序遍歷的順序是左子樹 -> 根節點 -> 右子樹。

使用遞迴來實現

按照左子樹 -> 根節點 -> 右子樹的順序訪問節點。

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

使用堆疊來實現

盡可能移動到左子節點，同時將父節點壓入堆疊。當無左子節點時，取出堆疊中的父節點訪問，然後移動到其右子節點。

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

            }
        }
        return ans;
    }
};

Morris Traversal 實現

嘗試將當前節點的左子樹中最右側的節點的右孩子指向當前節點，以建立臨時連結。當再次訪問同一節點時，恢復樹的結構並將節點值存入答案。

    class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> ans;
        TreeNode* curr = root;
        while(curr != NULL){
            if(curr->left == NULL){
                ans.push_back(curr->val);
                curr = curr->right;
            }
            else{
                TreeNode* pre = curr->left;
                while(pre->right != NULL && pre->right != curr)
                    pre = pre->right;
                if(pre->right == NULL){
                    pre->right = curr;
                    curr = curr->left;
                }
                else{
                    pre->right = NULL;
                    ans.push_back(curr->val);
                    curr = curr->right;
                }
            }
        }
        return ans;
    }
};

98. Validate Binary Search Tree

程度

Medium

題目

確定它是否是有效的二元搜尋樹

想法

二元搜尋樹定義 :
1.左子樹上所有節點的值都小於它的父節點的值。
2.右子樹上所有節點的值都大於它的父節點的值。

遞迴中序遍歷

我們可以使用遞迴來中序遍歷二叉搜尋樹，同時檢查每個節點的值是否位於一個合法的範圍內。具體來說，我們可以維護一個最小值和一個最大值，初始化為最小整數和最大整數，然後遞迴檢查每個節點的值是否在這個範圍內。如果是，則繼續遞迴檢查左子樹和右子樹。如果不是，則返回 false。

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        long long int min = -2147483649 ,max = 2147483648;
        return isBST(min ,root , max );
    }

    bool isBST(long long int min ,TreeNode* root , long long int max ){
        if(root==nullptr)
            return true;
        if(min < root->val && root->val < max)
            return isBST(min ,root->left , root->val ) && isBST(root->val , root->right , max);
        return false;
    }  
};

使用堆疊中序遍歷

另一種方法是使用堆疊進行中序遍歷，同時檢查遍歷的節點值是否嚴格遞增。如果遍歷的節點值不是嚴格遞增的，則返回 false。

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        stack<TreeNode*> s;
        vector<int> ans;
        TreeNode* curr = root;
        if(curr==nullptr)
            return true;
        while(curr!=nullptr || !s.empty()){
            if(curr !=nullptr){
                s.push(curr);
                curr = curr->left;
            }
            else{
                curr = s.top();
                s.pop();
                if(ans.size()>0 && ans[ans.size()-1] >= curr->val)
                    return false;
                else {
                    ans.push_back(curr->val);
                    curr = curr->right;
                }
                    
            }

        }
        return true;
    }  
};

102. Binary Tree Level Order Traversal

程度

Medium

題目

傳回其節點值的層序遍歷(即由左至右，逐級)

想法

遞迴

一種方法是使用遞迴，同時記錄每個節點的層級。如果該層級的數組還不存在，就新增一個數組。

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> ans;
        if(root == nullptr)
            return ans;
        
        levelorder_recursive(root,0,ans);
        return ans;
    }
    void levelorder_recursive(TreeNode* root,int level,vector<vector<int>> &ans){
        if(root == nullptr)
            return ;
        if(ans.size() == level) //new array
            ans.push_back(vector<int>());
        ans[level].push_back(root->val);
        levelorder_recursive(root->left,level+1,ans);
        levelorder_recursive(root->right,level+1,ans);
    }
};

迭代

另一種方法是使用迭代，利用一個隊列來處理節點，同時計算每一層的節點數。這樣可以確保節點按照從左到右的順序進行處理。

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> ans;
        if(root == nullptr)
            return ans;
        queue<TreeNode*>q;
        q.push(root);
        while(!q.empty()){

            vector<int> currentlevel;
            int currentsize  = q.size();
            while(currentsize--){
               TreeNode* ptr = q.front();
                q.pop();
                currentlevel.push_back(ptr->val);
                if(ptr->left != nullptr)
                    q.push(ptr->left);
                if(ptr->right != nullptr)
                    q.push(ptr->right);
            }
            ans.push_back(currentlevel);
           
        }
        return ans;
    }
};

有時候，我們可能需要改變思考方式，從不同的角度來看待問題，才能找到新的解決方案。 (今天的解法都不只一種)