104.二叉樹的最大深度

給定一個(gè)二叉樹喷户，找出其最大深度唾那。二叉樹的深度為根節(jié)點(diǎn)到最遠(yuǎn)葉子節(jié)點(diǎn)的最長路徑上的節(jié)點(diǎn)數(shù)。
思路一：遞歸DFS
每個(gè)節(jié)點(diǎn)的最大深度等于其左右子樹最大深度+1褪尝。
maxDepth(root)=max(maxDepth(root->left),maxDepth(root->right))+1

    int maxDepth(TreeNode* root) {
        if(!root)
            return 0;
        return max(maxDepth(root->left),maxDepth(root->right))+1;
    }

如果遞歸過深闹获，會(huì)產(chǎn)生很多臨時(shí)變量，導(dǎo)致棧溢出河哑。所以如何將遞歸的DFS轉(zhuǎn)為非遞歸避诽？遞歸轉(zhuǎn)為非遞歸通常用棧來實(shí)現(xiàn)。
思路二：非遞歸DFS

    int maxDepth(TreeNode* root) {
        if(!root)
            return 0;
        int mm=0;#最大深度
        stack<pair<TreeNode*,int>> s;#記錄每個(gè)節(jié)點(diǎn)的深度
        s.push({root,1});
        while(!s.empty())
        {
            pair<TreeNode*,int> t=s.top();
            s.pop();
            TreeNode* tmp=t.first;
            int n=t.second;
            if(n>mm)
                mm=n;
            if(tmp->left)
                s.push({tmp->left,n+1});
            if(tmp->right)
                s.push({tmp->right,n+1});
        }
        return mm;
    }

以上方法都是用DFS的方法灾馒，最直觀的方法是對(duì)二叉樹的每一層進(jìn)行遍歷茎用，即二叉樹的層序遍歷遣总，用的是BFS的方法睬罗，即使用隊(duì)列其求解。

102.二叉樹的層序遍歷

BFS旭斥，廣度/寬度優(yōu)先容达。說白了就是從上到下，先把每一層遍歷完之后再遍歷一下一層垂券。
層序遍歷可以用DFS的方法實(shí)現(xiàn)花盐，但是要保存每個(gè)節(jié)點(diǎn)的深度值，使用二元組 (node, level) 來表示狀態(tài)菇爪。而BFS不用算芯。

• 根元素入隊(duì)
• 當(dāng)隊(duì)列非空時(shí)
  - 求隊(duì)列長度
  - 該長度內(nèi)節(jié)點(diǎn)為同一深度
  - 下一級(jí)節(jié)點(diǎn)入隊(duì)

vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> result;
        if(!root)
            return result;
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty())
        {
            vector<int> cur;
            int l=q.size();
            for(int i=0;i<l;i++)
            {
                TreeNode* tmp=q.front();
                q.pop();
                cur.push_back(tmp->val);
                if(tmp->left) q.push(tmp->left);
                if(tmp->right) q.push(tmp->right);
            }
            result.push_back(cur);
        }
        return result;
    }

98.驗(yàn)證二叉搜索樹

二叉搜索樹的左子樹小于根節(jié)點(diǎn)，右子樹大于根節(jié)點(diǎn)凳宙。它的左熙揍、右子樹也分別為二叉搜索樹。
思路一：中序遍歷
因?yàn)槎鏄涞闹行虮闅v為遞增數(shù)列氏涩，所以只要判斷中序遍歷后是否遞增届囚。中序遍歷：左-》中-》右有梆。

 bool isValidBST(TreeNode* root) {
        vector<int> vec;
        midorder(root,vec);
        for(int i=0;i<vec.size()-1;i++)
        {
            if(vec[i]>=vec[i+1])
            return false;
        }
        return true;
    }
    void midorder(TreeNode* root,vector<int>& vec)
    {
        if(!root)
            return;
        midorder(root->left,vec);
        vec.push_back(root->val);
        midorder(root->right,vec);
    }

思路二：遞歸
錯(cuò)誤思想：如果左右子樹是二叉搜索樹，且左子樹根節(jié)點(diǎn)值小于中間節(jié)點(diǎn)意系，右子czz樹根節(jié)點(diǎn)的值大于中間節(jié)點(diǎn)泥耀，則可以判斷為BST。忽略了左右子樹內(nèi)的值與中間節(jié)點(diǎn)的大小比較蛔添。
左子樹保存節(jié)點(diǎn)最大值痰催，右子樹保存節(jié)點(diǎn)最小值，與中間節(jié)點(diǎn)比較可以解決迎瞧。

    bool isValidBST(TreeNode* root) {
        return isBST(root,LONG_MIN,LONG_MAX);
    }
    bool isBST(TreeNode* root,long mi,long ma)
    {
        if(!root)
            return 1;
        if((mi>=root->val)||(ma<=root->val))
            return 0;
        return isBST(root->left,mi,root->val) && isBST(root->right,root->val,ma);
    }

最大值最小值的數(shù)據(jù)類型為長整型陨囊。

700.二叉搜索樹查找

給定二叉搜索樹（BST）的根節(jié)點(diǎn)和一個(gè)值。你需要在BST中找到節(jié)點(diǎn)值等于給定值的節(jié)點(diǎn)夹攒。返回以該節(jié)點(diǎn)為根的子樹蜘醋。如果節(jié)點(diǎn)不存在，則返回 NULL咏尝。
思路一：迭代
比較給定值與根節(jié)點(diǎn)的大小压语，小于根節(jié)點(diǎn)找左子樹，大于根節(jié)點(diǎn)找右子樹编检，直到子節(jié)點(diǎn)為空胎食。

TreeNode* searchBST(TreeNode* root, int val) {
        TreeNode* new_node=root;
        while(new_node!=nullptr)
        {
            if(val==new_node->val)
                return new_node;
            if(val>new_node->val)
                new_node=new_node->right;
            else
                new_node=new_node->left;
        }
        return nullptr;
    }

思路二：遞歸

    TreeNode* searchBST(TreeNode* root, int val) {
        if(!root)
            return nullptr;
        if(val==root->val)
            return root;
        if(val>root->val)
            return searchBST(root->right,val);
        else
            return searchBST(root->left,val);
    }

思路二：遞歸

450.BST的刪除

給定一個(gè)二叉搜索樹的根節(jié)點(diǎn) root 和一個(gè)值 key，刪除二叉搜索樹中的 key 對(duì)應(yīng)的節(jié)點(diǎn)允懂，并保證二叉搜索樹的性質(zhì)不變厕怜。返回二叉搜索樹（有可能被更新）的根節(jié)點(diǎn)的引用。
一般來說蕾总，刪除節(jié)點(diǎn)可分為兩個(gè)步驟:
1.首先找到需要?jiǎng)h除的節(jié)點(diǎn)粥航；
2.如果找到了，刪除它生百。
說明： 要求算法時(shí)間復(fù)雜度為 O(h)递雀，h 為樹的高度。
難點(diǎn)：如何提前一步搜索蚀浆，刪除節(jié)點(diǎn)缀程。還要保持BTS的特性。

• 如果目標(biāo)節(jié)點(diǎn)大于當(dāng)前節(jié)點(diǎn)值市俊，則去右子樹中刪除杨凑；
• 如果目標(biāo)節(jié)點(diǎn)小于當(dāng)前節(jié)點(diǎn)值，則去左子樹中刪除摆昧；

• 如果目標(biāo)節(jié)點(diǎn)就是當(dāng)前節(jié)點(diǎn)撩满，分為以下三種情況：
  1.其無左子：其右子頂替其位置，刪除了該節(jié)點(diǎn)；
  2.其無右子：其左子頂替其位置鹦牛，刪除了該節(jié)點(diǎn)搞糕；
  3.其左右子節(jié)點(diǎn)都有：其左子樹轉(zhuǎn)移到其右子樹的最左節(jié)點(diǎn)的左子樹上，然后右子樹頂替其位置曼追，由此刪除了該節(jié)點(diǎn)窍仰。

  
  
  左右子節(jié)點(diǎn)都有.png

class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        if(!root)
            return root;
        if(key==root->val)//找到目標(biāo)節(jié)點(diǎn)
        {
            if(!root->right)
                return root->left;//讓左子樹代替該節(jié)點(diǎn)
            if(!root->left)
                return root->right;//讓右子樹代替該節(jié)點(diǎn)
            TreeNode* node =  root->right;//左右子樹都存在，左子樹移接到右子樹最左節(jié)點(diǎn)
            while(node->left){
                node=node->left;
            }
            node->left=root->left;//移花接木
            root=root->right;//根節(jié)點(diǎn)變?yōu)橛易訕?        }
        if(key>root->val)
            root->right=deleteNode(root->right, key);//目標(biāo)節(jié)點(diǎn)在右子樹
        else
            root->left=deleteNode(root->left, key);//目標(biāo)節(jié)點(diǎn)在左子樹
        return root;
    }
};

致謝：感謝知乎萬字長文礼殊！二叉樹入門和刷題看這篇就夠了！和梁先生的幫助晶伦！