對應letecode鏈接：
力扣
題目描述：
給你一個二叉樹的根節點 root ，判斷其是否是一個有效的二叉搜索樹，
有效 二叉搜索樹定義如下：
節點的左子樹只包含 小于 當前節點的數，
節點的右子樹只包含 大于 當前節點的數，
所有左子樹和右子樹自身必須也是二叉搜索樹，
示例 1：
輸入：root = [2,1,3]
輸出：true
示例 2：
輸入：root = [5,1,4,null,null,3,6]
輸出：false
解釋：根節點的值是 5 ，但是右子節點的值是 4 ，
提示：
樹中節點數目范圍在[1, 104] 內
-231 <= Node.val <= 231 - 1
解題思路：
1.當前節點的值是其左子樹的值的上界（最大值）
2.當前節點的值是其右子樹的值的下界（最小值）
所以我們在此引入上界與下界，用以保存之前的節點中出現的最大值與最小值
在每棵子樹，root 都是左子樹的上界，是右子樹的下界，只有當這兩者同時成立時，才可能確保是一顆二叉搜索樹，
對應代碼：
class Solution { public: bool isValidBST(TreeNode* root) { return traversal(root,LONG_LONG_MIN,LONG_LONG_MAX);//由于題目說節點的值可以取到整型最大或者最小所以我們用long long } bool traversal(TreeNode*root,long long min,long long max) { if(root==nullptr)//空樹為true { return true; } if(root->val<=min||root->val>=max)//不合法 { return false; } bool Leftret= traversal(root->left,min,(long long)(root->val));//檢查左子樹 if(!Leftret)return false; bool Rightret=traversal(root->right,(long long)(root->val),max);//檢查右子樹 return Rightret; } };
當然我們還可以使用中序遍歷：
定義一個類似于全域變數的preVal，先檢查左子樹是不是搜索二叉樹，當遞回完左子樹時判斷單前節點的值是否小于等于preval如果是則回傳false,不是則把當前節點的值給preval.
對應代碼：
class Solution { public: long long preVal=LONG_LONG_MIN; bool isValidBST(TreeNode* root) { if(!root)return true; bool isLeftBST=isValidBST(root->left);//檢查左子樹是不是 if(!isLeftBST){ return false; } if(root->val<=preVal){//不合法 return false; }else{ preVal=root->val; } return isValidBST(root->right);//檢查右子樹即可； } };
迭代法：
由于搜索二叉樹的中序遍歷是有序的所以我們可以比較相鄰的兩個數看是不是有序的，比較完整棵樹之后結果就出來了
class Solution { public: bool isValidBST(TreeNode* root) { TreeNode*pre=nullptr; stack<TreeNode*>stk; TreeNode*cur=root; while(!stk.empty()||cur){ while(cur){ stk.push(cur); cur=cur->left; } auto node=stk.top(); stk.pop(); if((pre!=nullptr)&&node->val<=pre->val){//前面一個比后面一個大違法搜索二叉樹的規則 return false; } pre=node; cur=node->right; } return true; } };
平衡二叉樹
對應letecode鏈接：
力扣
題目描述：
給定一個二叉樹，判斷它是否是高度平衡的二叉樹，
本題中，一棵高度平衡二叉樹定義為：
一個二叉樹每個節點 的左右兩個子樹的高度差的絕對值不超過 1 ，
示例 1：
輸入：root = [3,9,20,null,null,15,7]
輸出：true
示例 2：
輸入：root = [1,2,2,3,3,null,null,4,4]
輸出：false
示例 3：輸入：root = []
輸出：true提示：
樹中的節點數在范圍 [0, 5000] 內
-104 <= Node.val <= 104
解題思路：
1.對當前節點，分別求解左子樹和右子樹的深度，判斷左右子樹的高度差是否<=1，
2.利用了104題中求解二叉樹的深度的方法
3.然后再對當前節點的左子樹和右子樹做同樣操作，
對應代碼：
class Solution { public: int getdepth(TreeNode*root) {//求高度 if(root==nullptr) return 0; int len1=getdepth(root->left); int len2=getdepth(root->right); return len1>len2?len1+1:len2+1; } bool isBalanced(TreeNode* root) { if(root==nullptr) return true;//空樹為true; return abs(getdepth(root->left)-getdepth(root->right))<2&&isBalanced(root->left)&&isBalanced(root->right); } };
但是這樣時間復制度就非常的高為0(N^2)重復計算了很多，因此我們可以考慮后序遍歷定義一個變數flag初始值為true，在檢查子樹的程序中判斷平衡性，如果已經不平衡就終止遞回
對應代碼：
class Solution { public: bool flag=true; int TreeDepth(TreeNode*root){ if(!root||!flag)return 0;//！flag是為了終止遞回回傳什么都不重要 int leftDepth=TreeDepth(root->left);//求左子樹的高度 int rightDepth=TreeDepth(root->right);//求右子樹的高度 if(abs(leftDepth-rightDepth)>1){//不平衡 flag=false; } return max(leftDepth,rightDepth)+1; } bool isBalanced(TreeNode* root) { TreeDepth(root); return flag; } };
或者這樣也是可以的：
class Solution { public: bool _isBalanced(TreeNode*root,int&ph){ if(!root){ ph=0; return true; } int leftHight=0; if(!_isBalanced(root->left,leftHight))return false; int rightHight=0; if(!_isBalanced(root->right,rightHight))return false; ph=max(leftHight,rightHight)+1; return abs(leftHight-rightHight)<2; } bool isBalanced(TreeNode* root) { int _hight=0; return _isBalanced(root,_hight); } };
判斷一顆樹是否為滿二叉樹
思路：
將樹的節點都入隊
然后按照滿二叉樹每一層的節點個數控制節點出隊 如果每一層都滿足節點數控制 那么為滿二叉樹
只要存在一層不滿足出隊數量 就不是滿二叉樹
對應代碼：
bool isFullTree(TreeNode*root){ if(!root)return false;//空樹不是完全二叉樹 int num=1;//第一層一個節點 queue<TreeNode*>q; q.push(root); while(!q.empty()){ int i; for( i=0;i<num&&!q.empty();i++){ while(!q.empty()){ auto node=q.top(); q.pop(); if(node->left){ q.push(node->left); } if(node->right){ q.push(node->right); } } }//只要有一層出隊的個數小于num那么他就不是滿二叉樹 if(i<num){ return false; } else{ num*=2; } } return true; }
對應完全二叉樹的代碼和解題思路在我的二叉樹基礎篇有鐵子們可以取那里找找，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/382817.html
標籤：其他
下一篇：C語言 畫心形 程式員的簡單浪漫