94.給定一個(gè)二叉樹的根節(jié)點(diǎn) root ，返回它的 中序 遍歷。

錯(cuò)誤代碼：

    void search (TreeNode* root,vector<int>& result){
        if(!root)
            return;
        if(root->left)
            return search(root->left,result);
        result.push_back(root->val);
        if(root->right)
            return search(root->right,result);
    }
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        if(!root)
            return result;
        search (root,result);
        return result;
    }

輸入：[1,null,2,3]
輸出：[1,3]
預(yù)期結(jié)果：[1,3,2]

正確代碼：

    void inorder(TreeNode* root, vector<int>& res) {
        if (!root) {
            return;
        }
        inorder(root->left, res);
        res.push_back(root->val);
        inorder(root->right, res);
    }
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        inorder(root, res);
        return res;
    }

錯(cuò)誤分析：
1.return到底什么時(shí)候加？
有返回值的時(shí)候吧。
2.用不用判斷roor->left?
一般不用吧

226、翻轉(zhuǎn)二叉樹

錯(cuò)誤代碼：

    TreeNode* invertTree(TreeNode* root) {
        if(!root)
            return root;
        root->left=invertTree(root->right);
        root->right=invertTree(root->left);
        return root;
    }

正確代碼：

    TreeNode* invertTree(TreeNode* root) {
        if (root == nullptr) {
            return nullptr;
        }
        TreeNode* left = invertTree(root->left);
        TreeNode* right = invertTree(root->right);
        root->left = right;
        root->right = left;
        return root;
    }

錯(cuò)誤分析：
原 root.left 的指向已經(jīng)改變了？
如果先給root->left賦值，在計(jì)算root->right時(shí)，root->left已經(jīng)被改變了。所以，應(yīng)該先計(jì)算結(jié)果，再賦值，賦的值沒(méi)有被改變過(guò)。

543.二叉樹的直徑

給定一棵二叉樹，你需要計(jì)算它的直徑長(zhǎng)度。一棵二叉樹的直徑長(zhǎng)度是任意兩個(gè)結(jié)點(diǎn)路徑長(zhǎng)度中的最大值。這條路徑可能穿過(guò)也可能不穿過(guò)根結(jié)點(diǎn)。
給定二叉樹:

     1
    / \
   2   3
  / \     
 4   5    

返回 3, 它的長(zhǎng)度是路徑 [4,2,1,3] 或者 [5,2,1,3]。

知道使用遞歸，但是沒(méi)有想法。

思路：
兩個(gè)葉子節(jié)點(diǎn)之間的路徑=根節(jié)點(diǎn)到左右葉子結(jié)點(diǎn)的深度之和。
所以首先，我們要寫出一個(gè)求深度的函數(shù)，這里用到深度優(yōu)先搜索。

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

之后，設(shè)置一個(gè)變量來(lái)儲(chǔ)存最大路徑，對(duì)每一個(gè)節(jié)點(diǎn)，都把它左右子樹深度相加，然后與該變量進(jìn)行比較。

    int maxd=0;
    int depth(TreeNode* root)
    {
        if(!root)
            return 0;
        int L=depth(root->left);
        int R=depth(root->right);
        if(maxd<L+R)
            maxd=L+R;
        return max(L,R)+1;
    }
    int diameterOfBinaryTree(TreeNode* root) {
        if(!root)
            return 0;
        depth(root);
        return maxd;
    }

主要是沒(méi)想到把計(jì)算每個(gè)節(jié)點(diǎn)最大路徑放在計(jì)算深度的函數(shù)里。
錯(cuò)誤代碼：

        if(maxd<depth(root->left)+depth(root->right))
            maxd=depth(root->left)+depth(root->right);
        return max(depth(root->left),depth(root->right))+1;

這種情況相當(dāng)于遞歸了三次，會(huì)導(dǎo)致超時(shí)！