二叉樹

打算先來了解二叉樹基礎，都是簡單題，目的是熟悉代碼格式和解題基礎思路。

1、二叉樹最大深度

二叉樹最大深度

方法一、深度搜索

直接用原函數做遞歸，比較簡單

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:int maxDepth(TreeNode* root) {if(root ==nullptr)return 0;return max(maxDepth(root->left), maxDepth(root->right))+1;}
};

方法二、廣度搜索

• 利用queue來存儲每一層的節點
• 每層次循環是當前queue的長度，用一個數來記錄，一般是2的次方，然后再將新的數放置queue末尾。

class Solution {
public:int maxDepth(TreeNode* root) {if(root==nullptr)return 0;queue<TreeNode*> Q;Q.push(root);int depth = 0;while(!Q.empty()){int sz=Q.size();while(sz>0){TreeNode* node= Q.front();Q.pop();if(node->left)Q.push(node->left);if(node->right)Q.push(node->right);sz-=1;}depth+=1;}return depth;}
};

2、相同的樹

相同的樹

方法一、前序遍歷比較

這是自己寫的，思路是確定可以用遞歸，這個是深度搜索
然后先判斷節點存在，再判斷是否正確

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:bool isSameTree(TreeNode* p, TreeNode* q) {bool a=true,b=true;if(p==nullptr&&q==nullptr)return true;else if(p!=nullptr&&q==nullptr)return false;else if(p==nullptr&&q!=nullptr)return false;else{if(p->val!=q->val)return false;a=isSameTree(p->left,q->left);b=isSameTree(p->right,q->right);}if(a==false||b==false)return false;else return true;}
};

方法二、廣度搜索

來自官方題解中的一種有點復雜。

class Solution {  
public:  // 檢查兩棵二叉樹是否相同  bool isSameTree(TreeNode* p, TreeNode* q) {  // 如果兩棵樹都為空，返回 true  if (p == nullptr && q == nullptr) {  return true;  }   // 如果一棵樹為空而另一棵樹不為空，返回 false  else if (p == nullptr || q == nullptr) {  return false;  }  // 創建兩個隊列用于廣度優先搜索（BFS）  queue<TreeNode*> queue1, queue2;  queue1.push(p); // 將第一個樹的根節點入隊  queue2.push(q); // 將第二個樹的根節點入隊  // 當兩個隊列都不為空時，繼續比較  while (!queue1.empty() && !queue2.empty()) {  // 取出兩個隊列的前端節點進行比較  auto node1 = queue1.front();  queue1.pop();  auto node2 = queue2.front();  queue2.pop();  // 比較兩個節點的值  if (node1->val != node2->val) {  return false; // 值不相同，則樹不相同  }  // 獲取當前節點的左右子節點  auto left1 = node1->left, right1 = node1->right;  auto left2 = node2->left, right2 = node2->right;  // 檢查左右子節點是否存在不一致  if ((left1 == nullptr) ^ (left2 == nullptr)) {  return false; // 只有一棵樹有左子節點  }  if ((right1 == nullptr) ^ (right2 == nullptr)) {  return false; // 只有一棵樹有右子節點  }  // 如果左右子節點存在，則將其加入隊列中  if (left1 != nullptr) {  queue1.push(left1); // 將第一個樹的左子節點添加到隊列  }  if (right1 != nullptr) {  queue1.push(right1); // 將第一個樹的右子節點添加到隊列  }  if (left2 != nullptr) {  queue2.push(left2); // 將第二個樹的左子節點添加到隊列  }  if (right2 != nullptr) {  queue2.push(right2); // 將第二個樹的右子節點添加到隊列  }  }  // 返回兩個隊列是否都為空（即兩棵樹的結構是否相同）  return queue1.empty() && queue2.empty();  }  
};

3、翻轉二叉樹

翻轉二叉樹

方法一、

用遞歸找到最下方的左右子樹，直接更換節點而不是值

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public: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;}
};

4、對稱二叉樹

101.對稱二叉樹

方法一、廣度匹配

也就是迭代求解，下面是我自己寫的復雜的代碼，因為本能覺得可以把每一層，存儲為一個vector，然后再綜合比較。但是實現起來略顯復雜

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:bool isSymmetric(TreeNode* root) {queue<TreeNode*> tree_level;vector<int> num_level;vector<int> num_level_re;int level=1;if(root->left==nullptr&&root->right==nullptr)return true;else if(root->left!=nullptr&&root->right!=nullptr){level=1;}else return false;tree_level.push(root->left);num_level.push_back(root->left->val);tree_level.push(root->right);num_level.push_back(root->right->val);while(tree_level.size()!=0){num_level_re=num_level;reverse(num_level_re.begin(),num_level_re.end());for(int i=0;i<num_level.size();i++){if(num_level[i]==num_level_re[i])continue;else return false;}num_level.clear();num_level_re.clear();// 把每層都節點和元素加入int level1 = tree_level.size();while(level1>0){TreeNode* root_now;root_now = tree_level.front();tree_level.pop();if(root_now->left!=nullptr){tree_level.push(root_now->left);num_level.push_back(root_now->left->val);}else num_level.push_back(-1);if(root_now->right!=nullptr){tree_level.push(root_now->right);num_level.push_back(root_now->right->val);}else num_level.push_back(-1);level1--;}// 判斷每層不能為奇數if(tree_level.size()%2!=0)return false;  level++;}return true;}
};

方法二、精簡迭代法

其思路是：特地寫一個輔助函數，可以同時輸入左右子樹，這樣更加方便做迭代

class Solution {
public:bool check(TreeNode *u, TreeNode *v) {queue <TreeNode*> q;q.push(u); q.push(v);while (!q.empty()) {u = q.front(); q.pop();v = q.front(); q.pop();if (!u && !v) continue;if ((!u || !v) || (u->val != v->val)) return false;q.push(u->left); q.push(v->right);q.push(u->right); q.push(v->left);}return true;}bool isSymmetric(TreeNode* root) {return check(root, root);}
};

方法三、遞歸法

比較難想到，下面是解釋
也需要輔助函數， 然后最左的和最右的分別組成對對比

class Solution {
public:// 輔助函數：檢查兩個子樹是否對稱bool check(TreeNode *leftNode, TreeNode *rightNode) {// 情況 1：兩個節點都為空if (leftNode == nullptr && rightNode == nullptr) {return true; // 空節點是對稱的}// 情況 2：其中一個節點為空，另一個不為空if (leftNode == nullptr || rightNode == nullptr) {return false; // 不對稱}// 情況 3：兩個節點的值不相等if (leftNode->val != rightNode->val) {return false; // 不對稱}// 遞歸檢查：// 1. 左子樹的左節點和右子樹的右節點是否對稱// 2. 左子樹的右節點和右子樹的左節點是否對稱bool isOuterSymetric = check(leftNode->left, rightNode->right);  // 檢查外層bool isInnerSymetric = check(leftNode->right, rightNode->left); // 檢查內層// 只有外層和內層都對稱，整個樹才對稱return isOuterSymetric && isInnerSymetric;}// 主函數：判斷二叉樹是否對稱bool isSymmetric(TreeNode* root) {// 如果根節點為空，直接返回 true（空樹是對稱的）if (root == nullptr) {return true;}// 檢查左子樹和右子樹是否對稱return check(root->left, root->right);}
};