樹專題

LC98驗證二叉搜索樹

1.分析 2.代碼
給定一個二叉樹，判斷其是否是一個有效的二叉搜索樹。

假設(shè)一個二叉搜索樹具有如下特征：

節(jié)點的左子樹只包含小于當前節(jié)點的數(shù)。
節(jié)點的右子樹只包含大于當前節(jié)點的數(shù)。
所有左子樹和右子樹自身必須也是二叉搜索樹。
示例 1:

輸入:
2
/
1 3
輸出: true

image.png

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        return dfs(root,INT_MIN,INT_MAX);
    }
    
    bool dfs(TreeNode* root,long long mmin,long long mmax)//傳入LONG類型
    {
        if(!root) return true;//當前子樹為空，一定可以滿足條件，返回TRUE
        if(root->val<mmin||root->val>mmax) return false; //先判根節(jié)點是不是滿足，不合法
        //若根節(jié)點滿足，則考慮左右子樹是否滿足，用遞歸，找到合適的區(qū)間范圍
        return dfs(root->left,mmin,root->val-1ll)&&dfs(root->right,root->val+1ll,mmax);//1ll指value負無窮溢出，所以用LL
    }
};

LC94 二叉樹的中序遍歷

給定一個二叉樹，返回它的中序 遍歷。

示例:

輸入: [1,null,2,3]
1

2
/
3

輸出: [1,3,2]
1、分析 采用迭代算法
采用非遞歸方法完成。即需要一個棧來模擬整個過程。先把整個樹壓棧，即把樹的最左邊那一條鏈上的節(jié)點都壓入棧，再依次從棧頂彈出元素，每次判斷一下此節(jié)點是否有右子樹，若有則把右子樹整個壓棧，而把整個右子樹壓棧的動作就是和最初把整個樹壓棧一樣。
寫遞歸其實是系統(tǒng)開棧幫助我們模擬。
我們自己用棧來模擬，先把最左邊的鏈全部放入棧中，若沒有右子樹，就回到上一層，中序就是遍歷了跟之后遍歷右子樹，迭代很常見在樹中，前序遍歷和后序遍歷是完全對稱的。

class Solution {
public:
    vector<int> ans;
    vector<int> inorderTraversal(TreeNode* root) {
        stack<TreeNode*> s;//定義一個棧
        if(!root) return ans;//
        while(root||s.size())//不為空
        {
            while(root) //把樹的最左邊一條鏈上的節(jié)點壓棧
            {
                s.push(root);
                root=root->left;
            }
            auto p=s.top();  //取出棧頂元素
            ans.push_back(p->val);
            s.pop();
            root=p->right;  //讓此棧頂元素的整個右子樹壓棧
        }
        return ans;
    }