94.給定一個二叉樹的根節(jié)點 root 酱酬，返回它的 中序 遍歷壶谒。
錯誤代碼：
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;
}
錯誤分析：
1.return到底什么時候加？
有返回值的時候吧膳沽。
2.用不用判斷roor->left?
一般不用吧
226汗菜、翻轉(zhuǎn)二叉樹
錯誤代碼：
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;
}
錯誤分析：
原 root.left 的指向已經(jīng)改變了？
如果先給root->left賦值挑社，在計算root->right時陨界，root->left已經(jīng)被改變了。所以痛阻，應(yīng)該先計算結(jié)果菌瘪，再賦值，賦的值沒有被改變過阱当。
543.二叉樹的直徑
給定一棵二叉樹俏扩，你需要計算它的直徑長度。一棵二叉樹的直徑長度是任意兩個結(jié)點路徑長度中的最大值弊添。這條路徑可能穿過也可能不穿過根結(jié)點动猬。
給定二叉樹:
1 / \ 2 3 / \ 4 5
返回 3, 它的長度是路徑 [4,2,1,3] 或者 [5,2,1,3]。
知道使用遞歸表箭，但是沒有想法赁咙。
思路：
兩個葉子節(jié)點之間的路徑=根節(jié)點到左右葉子結(jié)點的深度之和。
所以首先免钻，我們要寫出一個求深度的函數(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è)置一個變量來儲存最大路徑凤覆，對每一個節(jié)點，都把它左右子樹深度相加拆魏，然后與該變量進行比較盯桦。
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;
}
主要是沒想到把計算每個節(jié)點最大路徑放在計算深度的函數(shù)里慈俯。
錯誤代碼：
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)于遞歸了三次，會導(dǎo)致超時拥峦！
