搜索二叉樹的后序遍歷
對應letecode鏈接：
https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof/
題目描述：
輸入一個整數陣列，判斷該陣列是不是某二叉搜索樹的后序遍歷結果，如果是則回傳 true，否則回傳 false，假設輸入的陣列的任意兩個數字都互不相同，
參考以下這顆二叉搜索樹：
5
/ \
2 6
/ \
1 3
示例 1：輸入: [1,6,3,2,5]
輸出: false
示例 2：輸入: [1,3,2,6,5]
輸出: true
解題思路：
利用搜索二叉樹的性質：
節點的左子樹只包含 小于 當前節點的數，
節點的右子樹只包含 大于 當前節點的數，
所有左子樹和右子樹自身必須也是二叉搜索樹，
比如下面這棵二叉樹，他的后續遍歷是：[3，5，4，10，12，9]
們知道后續遍歷的最后一個數字一定是根節點，所以陣列中最后一個數字9就是根節點，我們從前往后找到第一個比9大的數字10，那么10后面的[10，12]（除了9）都是9的右子節點，10前面的[3，5，4]都是9的左子節點，后面的需要判斷一下，如果有小于9的，說明不是二叉搜索樹，直接回傳false，然后再以遞回的方式判斷左右子樹，
再來看一個，他的后續遍歷是[3，5，13，10，12，9]
我們來根據陣列拆分，第一個比9大的后面都是9的右子節點[13，10，12]，然后再拆分這個陣列，12是根節點，第一個比12大的后面都是12的右子節點[13，10]，但我們看到10是比12小的，他不可能是12的右子節點，所以我們能確定這棵樹不是二叉搜索樹
對應代碼：
class Solution { public: bool verifyPostorder(vector<int>& postorder) { return CheckBST(postorder,0,postorder.size()-1); } bool CheckBST(vector<int>&postorder,int left,int right){ if(left>=right)return true; //如果left==right，就一個節點不需要判斷了，如果left>right說明沒有節點， //也不用再看了,否則就要繼續往下判斷 int mid=left; int key=postorder[right]; //因為陣列中最后一個值postorder[right]是根節點，這里從左往右找出第一個比 //根節點大的值，他后面的都是根節點的右子節點（包含當前值，不包含最后一個值， //因為最后一個是根節點），他前面的都是根節點的左子節點 while(mid<=right&&postorder[mid]<key){ mid++; } //因為postorder[mid]前面的值都是比根節點root小的， //我們還需要確定postorder[mid]后面的值都要比根節點root大， //如果后面有比根節點小的直接回傳false int tmp=mid; while(tmp<=right){ if(postorder[tmp]<key)return false; tmp++; } //對左右子樹進行遞回呼叫 return CheckBST(postorder,left,mid-1)&&CheckBST(postorder,mid,right-1); } };
最近公共祖先
對應letecode鏈接：
https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/
題目描述：
給定一個二叉樹, 找到該樹中兩個指定節點的最近公共祖先，
百度百科中最近公共祖先的定義為：“對于有根樹 T 的兩個節點 p、q，最近公共祖先表示為一個節點 x，滿足 x 是 p、q 的祖先且 x 的深度盡可能大（一個節點也可以是它自己的祖先），”
示例 1：
輸入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
輸出：3
解釋：節點 5 和節點 1 的最近公共祖先是節點 3 ，
示例 2：
輸入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
輸出：5
解釋：節點 5 和節點 4 的最近公共祖先是節點 5 ，因為根據定義最近公共祖先節點可以為節點本身，
示例 3：輸入：root = [1,2], p = 1, q = 2
輸出：1提示：
樹中節點數目在范圍 [2, 105] 內，
-109 <= Node.val <= 109
所有 Node.val 互不相同 ，
p != q
p 和 q 均存在于給定的二叉樹中，
解題思路：
情況一：root為p,q中的一個，這時公共祖先為root
情況二：p,q分別在root的左右子樹上（p在左子樹，q在右子樹；還是p在右子樹，q在左子樹的情況都統一放在一起考慮）這時滿足p,q的最近公共祖先的結點也只有root本身
情況三：p和q同時在root的左子樹；這時確定最近公共祖先需要遍歷子樹來進行遞回求解，情況四：p,q同時在root的右子樹，這時確定最近公共祖先需要遍歷子樹進行遞回求解
對應代碼：
class Solution { public: TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { if(!root||root==q||root==p)return root;//p，q之中有一個是root則root是公共祖先 TreeNode* pqInLeft=lowestCommonAncestor(root->left,p,q); //去左子樹找 TreeNode*pqInRight=lowestCommonAncestor(root->right,p,q); //去右子樹找 if(pqInLeft==NULL)return pqInRight; //如果左子樹沒找到q,p則一定在右子樹 if(pqInRight==NULL)return pqInLeft; //如果右子樹沒找到p,q則一定在左子樹上 return root; //如果左子樹和右子樹各找到一個說明root為公共祖先 } };
剛開始的時候我是這么想的：
1.定義一個函式Find先去左子樹找一個p，去右子樹上找一下q
2.看p和q是否同時在左邊是否同時在右邊，如果同時在左邊則遞回去左子樹去找如果在右邊則遞回去右子樹找，如果既不同時在左子樹又不同時在右子樹那么root就是最近公共祖先，
對應代碼：
class Solution { public: TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { if(root==p||root==q)return root; bool pInLeft=Find(root->left,p); bool pInRight=!pInLeft; //如果左邊找到了p那么右邊肯定找不到這是相反的關系 bool qInLeft=Find(root->left,q); bool qInRigt=!qInLeft; //如果左邊找到了p那么右邊肯定找不到這是相反的關系 if(pInLeft&&qInLeft)return lowestCommonAncestor(root->left,p,q); //同時在左邊則去左邊找 if(pInRight&&qInRigt)return lowestCommonAncestor(root->right,p,q); //同時在右邊則去右邊找 return root; //一個在左邊一個在右邊root為最近公共祖先 } bool Find(TreeNode*root,TreeNode*node){ if(!root)return false;//空樹表示找不到 if(root==node)return true; bool leftRet=Find(root->left,node);//先去左樹找 if(leftRet)return leftRet;//左樹找到了回傳不用找了 bool rightRet=Find(root->right,node);//左樹沒找到右樹找 if(rightRet)return rightRet;//右樹找到了 return false;//左樹右樹都沒找到 } };
非遞回：
要想找到兩個節點的最近公共祖先節點，我們可以從兩個節點往上找，每個節點都往上走，一直走到根節點，那么根節點到這兩個節點的連線肯定有相交的地方，如果是從上往下走，那么最后一次相交的節點就是他們的最近公共祖先節點，我們就以找6和7的最近公共節點來畫個圖看一下
我們看到6和7公共祖先有5和3，但最近的是5，我們只要往上找，找到他們第一個相同的公共祖先節點即可，但怎么找到每個節點的父節點呢，我們只需要把每個節點都遍歷一遍，然后順便記錄他們的父節點存盤在Map中，我們先找到其中的一條路徑，比如6→5→3，然后在另一個節點往上找，由于7不在那條路徑上，我們找7的父節點是2，2也不在那條路徑上，我們接著往上找，2的父節點是5，5在那條路徑上，所以5就是他們的最近公共子節點，
其實這里我們可以優化一下，我們沒必要遍歷所有的結點，我們一層一層的遍歷（也就是BFS），只需要這兩個節點都遍歷到就可以了，比如上面2和8的公共結點，我們只需要遍歷到第3層，把2和8都遍歷到就行了，沒必要再遍歷第4層了，
對應代碼：
class Solution { public: TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { unordered_map<TreeNode*,TreeNode*>parent;//記錄遍歷到的每個節點的父親 queue<TreeNode*>Q; Q.push(root); //根節點沒有父節點，所以為空 parent.insert(make_pair(root,nullptr)); while(!parent.count(p)||!parent.count(q)){//找到p,q就可以了 auto node=Q.front();//佇列中取資料 Q.pop(); if(node->left){//和層序遍歷一樣左不為空加入佇列 parent.insert(make_pair(node->left,node)); Q.push(node->left); } if(node->right){//右不為空加入佇列 parent.insert(make_pair(node->right,node)); Q.push(node->right); } } unordered_set<TreeNode*>anscetor; while(p){ anscetor.insert(p);//將p及他的祖先放入set中 p=parent[p]; } while(!anscetor.count(q)){//檢查是否相交相交就停止回圈 q=parent[q]; } return q; } };
二叉搜索樹的最近公共祖先
對應letecode鏈接：
https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-search-tree/
題目描述：
給定一個二叉搜索樹, 找到該樹中兩個指定節點的最近公共祖先，
百度百科中最近公共祖先的定義為：“對于有根樹 T 的兩個結點 p、q，最近公共祖先表示為一個結點 x，滿足 x 是 p、q 的祖先且 x 的深度盡可能大（一個節點也可以是它自己的祖先），”
例如，給定如下二叉搜索樹: root = [6,2,8,0,4,7,9,null,null,3,5]
示例 1:
輸入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
輸出: 6
解釋: 節點 2 和節點 8 的最近公共祖先是 6，
示例 2:輸入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
輸出: 2
解釋: 節點 2 和節點 4 的最近公共祖先是 2, 因為根據定義最近公共祖先節點可以為節點本身，
同樣的我們可以使用上題的方法在這題同樣可以過：
class Solution { public: TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { if(!root||root==q||root==p){ return root; } TreeNode*pqInLeft=lowestCommonAncestor(root->left,p,q); TreeNode*pqInRight=lowestCommonAncestor(root->right,p,q); if(!pqInLeft){ return pqInRight; } if(!pqInRight){ return pqInLeft; } return root; } };
我們也可以利用它是一顆搜索二叉樹：
對應代碼：
class Solution { public: TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { if(root->val<p->val&&root->val<q->val){//都在左邊 return lowestCommonAncestor(root->right,p,q); } if(root->val>p->val&&root->val>q->val){//都在右邊 return lowestCommonAncestor(root->left,p,q); } return root;//一個在左邊一個在右邊 } };
迭代方式：
class Solution { public: TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { while(root){ if(root->val>q->val&&root->val>p->val){ root=root->left; } else if(root->val<p->val&&root->val<q->val){ root=root->right; } else{ break; } } return root; } };
最后：🙌🙌🙌🙌
結語：對于個人來講，在leetcode上進行探索以及單人闖關是一件有趣的時間，一個程式員，如果不喜歡編程，那么可能就失去了這份職業的樂趣，刷到我的文章的人，我希望你們可以駐足一小會，忙里偷閑的閱讀一下我的文章，可能文章的內容對你來說很簡單，(^▽^)不過文章中的每一個字都是我認真專注的見證！希望您看完之后，若是能幫到您，勞煩請您簡單動動手指鼓勵我，我必回報更大的付出~
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/384272.html
標籤：其他