104.二叉樹的最大深度

給定一個二叉樹，找出其最大深度。二叉樹的深度為根節(jié)點到最遠葉子節(jié)點的最長路徑上的節(jié)點數(shù)。
思路一：遞歸DFS
每個節(jié)點的最大深度等于其左右子樹最大深度+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;
    }

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

    int maxDepth(TreeNode* root) {
        if(!root)
            return 0;
        int mm=0;#最大深度
        stack<pair<TreeNode*,int>> s;#記錄每個節(jié)點的深度
        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的方法，最直觀的方法是對二叉樹的每一層進行遍歷，即二叉樹的層序遍歷，用的是BFS的方法，即使用隊列其求解。

102.二叉樹的層序遍歷

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

• 根元素入隊
• 當隊列非空時
  - 求隊列長度
  - 該長度內(nèi)節(jié)點為同一深度
  - 下一級節(jié)點入隊

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.驗證二叉搜索樹

二叉搜索樹的左子樹小于根節(jié)點，右子樹大于根節(jié)點。它的左、右子樹也分別為二叉搜索樹。
思路一：中序遍歷
因為二叉樹的中序遍歷為遞增數(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);
    }

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

    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é)點和一個值。你需要在BST中找到節(jié)點值等于給定值的節(jié)點。返回以該節(jié)點為根的子樹。如果節(jié)點不存在，則返回 NULL。
思路一：迭代
比較給定值與根節(jié)點的大小，小于根節(jié)點找左子樹，大于根節(jié)點找右子樹，直到子節(jié)點為空。

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的刪除

給定一個二叉搜索樹的根節(jié)點 root 和一個值 key，刪除二叉搜索樹中的 key 對應的節(jié)點，并保證二叉搜索樹的性質(zhì)不變。返回二叉搜索樹（有可能被更新）的根節(jié)點的引用。
一般來說，刪除節(jié)點可分為兩個步驟:
1.首先找到需要刪除的節(jié)點；
2.如果找到了，刪除它。
說明： 要求算法時間復雜度為 O(h)，h 為樹的高度。
難點：如何提前一步搜索，刪除節(jié)點。還要保持BTS的特性。

• 如果目標節(jié)點大于當前節(jié)點值，則去右子樹中刪除；
• 如果目標節(jié)點小于當前節(jié)點值，則去左子樹中刪除；

• 如果目標節(jié)點就是當前節(jié)點，分為以下三種情況：
  1.其無左子：其右子頂替其位置，刪除了該節(jié)點；
  2.其無右子：其左子頂替其位置，刪除了該節(jié)點；
  3.其左右子節(jié)點都有：其左子樹轉(zhuǎn)移到其右子樹的最左節(jié)點的左子樹上，然后右子樹頂替其位置，由此刪除了該節(jié)點。

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

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

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