DAY22

654最大二叉樹

自己做的時候忽略了：nums.length>=1的題給條件。所以每次遞歸都要判斷是否size()>=1，不要空的。

1. /**
2. ?*?Definition?for?a?binary?tree?node.
3. ?*?struct?TreeNode?{
4. ?*?????int?val;
5. ?*?????TreeNode?*left;
6. ?*?????TreeNode?*right;
7. ?*?????TreeNode()?:?val(0),?left(nullptr),?right(nullptr)?{}
8. ?*?????TreeNode(int?x)?:?val(x),?left(nullptr),?right(nullptr)?{}
9. ?*?????TreeNode(int?x,?TreeNode?*left,?TreeNode?*right)?:?val(x),?left(left),?right(right)?{}
10. ?*?};
11. ?*/
12. class?Solution?{
13. public:
14. ????TreeNode*?constructMaximumBinaryTree(vector<int>&?nums)?{
15. ????????TreeNode*?node=new?TreeNode(0);
16. ????????if(nums.size()==1)?{
17. ????????????node->val=nums[0];
18. ????????????return?node;
19. ????????}
20. ????????int?index=0;
21. ????????for(int?i=1;i<nums.size();i++)
22. ????????{
23. ????????????if(nums[index]<nums[i])?index=i;
24. ????????}
25. ????????node->val=nums[index];
26. ????????if(index>0){
27. ????????????vector<int>?ln(nums.begin(),nums.begin()+index);
28. ????????????node->left=constructMaximumBinaryTree(ln);
29. ????????}
30. ????????if(index<nums.size()-1){
31. ????????????vector<int>?rn(nums.begin()+index+1,nums.end());
32. ????????????node->right=constructMaximumBinaryTree(rn);
33. ????????}
34. ????????return?node;
35. ????}
36. };

617合并二叉樹

遞歸之前，先弄明白遍歷順序很重要：

1. /**
2. ?*?Definition?for?a?binary?tree?node.
3. ?*?struct?TreeNode?{
4. ?*?????int?val;
5. ?*?????TreeNode?*left;
6. ?*?????TreeNode?*right;
7. ?*?????TreeNode()?:?val(0),?left(nullptr),?right(nullptr)?{}
8. ?*?????TreeNode(int?x)?:?val(x),?left(nullptr),?right(nullptr)?{}
9. ?*?????TreeNode(int?x,?TreeNode?*left,?TreeNode?*right)?:?val(x),?left(left),?right(right)?{}
10. ?*?};
11. ?*/
12. class?Solution?{
13. public:
14. ????TreeNode*?mergeTrees(TreeNode*?root1,?TreeNode*?root2)?{
15. ????????if(root1==nullptr)?return?root2;
16. ????????if(root2==nullptr)?return?root1;
17. ????????root1->val+=root2->val;
18. ????????root1->left=mergeTrees(root1->left,root2->left);
19. ????????root1->right=mergeTrees(root1->right,root2->right);
20. ????????return?root1;
21. ????}
22. };

700二叉搜索樹中的搜索

先寫迭代法，返璞歸真咯：

1. /**
2. ?*?Definition?for?a?binary?tree?node.
3. ?*?struct?TreeNode?{
4. ?*?????int?val;
5. ?*?????TreeNode?*left;
6. ?*?????TreeNode?*right;
7. ?*?????TreeNode()?:?val(0),?left(nullptr),?right(nullptr)?{}
8. ?*?????TreeNode(int?x)?:?val(x),?left(nullptr),?right(nullptr)?{}
9. ?*?????TreeNode(int?x,?TreeNode?*left,?TreeNode?*right)?:?val(x),?left(left),?right(right)?{}
10. ?*?};
11. ?*/
12. class?Solution?{
13. public:
14. ????TreeNode*?searchBST(TreeNode*?root,?int?val)?{
15. ????????while(root!=nullptr)
16. ????????{
17. ????????????if(root->val<val)?root=root->right;
18. ????????????else?if(root->val>val)?root=root->left;
19. ????????????else?return?root;
20. ????????}
21. ????????return?nullptr;
22. ????}
23. };

遞歸試試：

遞歸還是寫不出來，早上看過答案也寫不出來，邏輯理不清，什么時候該創建變量去接住遞歸的結果？

1. /**
2. ?*?Definition?for?a?binary?tree?node.
3. ?*?struct?TreeNode?{
4. ?*?????int?val;
5. ?*?????TreeNode?*left;
6. ?*?????TreeNode?*right;
7. ?*?????TreeNode()?:?val(0),?left(nullptr),?right(nullptr)?{}
8. ?*?????TreeNode(int?x)?:?val(x),?left(nullptr),?right(nullptr)?{}
9. ?*?????TreeNode(int?x,?TreeNode?*left,?TreeNode?*right)?:?val(x),?left(left),?right(right)?{}
10. ?*?};
11. ?*/
12. class?Solution?{
13. public:
14. ????TreeNode*?searchBST(TreeNode*?root,?int?val)?{
15. ????????if(root==nullptr||root->val==val)?return?root;
16. ????????TreeNode*?result=nullptr;
17. ????????if(root->val<val)?{
18. ????????????result=searchBST(root->right,val);
19. ????????}
20. ????????if(root->val>val){
21. ????????????result=searchBST(root->left,val);
22. ????????}
23. ????????return?result;
24. ????}
25. };

遞歸沒接住（沒找到），就返回的是初始化的result=nullptr;

98驗證二叉搜索樹

有很多陷阱在里面。迭代法就很容易出錯。

這里要知道并利用這個性質：二叉搜索樹的中序遍歷序列是嚴格單調增的數組。

1. /**
2. ?*?Definition?for?a?binary?tree?node.
3. ?*?struct?TreeNode?{
4. ?*?????int?val;
5. ?*?????TreeNode?*left;
6. ?*?????TreeNode?*right;
7. ?*?????TreeNode()?:?val(0),?left(nullptr),?right(nullptr)?{}
8. ?*?????TreeNode(int?x)?:?val(x),?left(nullptr),?right(nullptr)?{}
9. ?*?????TreeNode(int?x,?TreeNode?*left,?TreeNode?*right)?:?val(x),?left(left),?right(right)?{}
10. ?*?};
11. ?*/
12. class?Solution?{
13. private:
14. ????vector<int>?result;
15. ????void?exc(TreeNode?*root)
16. ????{
17. ????????if(root==nullptr)?return;
18. ????????exc(root->left);
19. ????????result.push_back(root->val);
20. ????????exc(root->right);
21. ????}
22. public:
23. ????bool?isValidBST(TreeNode*?root)?{
24. ????????result.clear();
25. ????????exc(root);
26. ????????for(int?i=1;i<result.size();i++)
27. ????????{
28. ????????????if(result[i-1]>=result[i])?return?false;
29. ????????}
30. ????????return?true;
31. ????}
32. };