代碼隨想錄算法訓練營：14/60

非科班學習算法day14?| LeetCode266:翻轉二叉樹?，Leetcode101: 對稱二叉樹，Leetcode100:相同的的樹?，LeetCode572:另一顆樹的子樹，LeetCode104：二叉樹的最大深度，LeetCode559：N叉樹的最大深度

介紹

一、基礎概念補充：

1.二叉樹的深度和高度??

二、LeetCode題目

1.Leetcode226: 翻轉二叉樹

題目解析

2.Leetcode101: 對稱二叉樹

題目解析

3.Leetcode100:相同的樹?

題目解析

4.Leetcode572:另一棵樹的子樹?

題目解析

5.Leetcode104: 二叉樹的最大深度

題目解析

6.Leetcode559: N叉樹的最大深度

題目解析

總結

介紹

包含LC的幾道題目，還有相應概念的補充。

相關圖解和更多版本：

代碼隨想錄 (programmercarl.com)https://programmercarl.com/#%E6%9C%AC%E7%AB%99%E8%83%8C%E6%99%AF

一、基礎概念補充：

1.二叉樹的深度和高度??

代碼隨想錄 (programmercarl.com)https://programmercarl.com/0104.%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E6%9C%80%E5%A4%A7%E6%B7%B1%E5%BA%A6.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE

二、LeetCode題目

1.Leetcode226: 翻轉二叉樹

題目鏈接：226. 翻轉二叉樹 - 力扣（LeetCode）

題目解析

? ? ? ?單層邏輯：交換左右兩個孩子節點，所以采用后序遍歷或者前序遍歷都可以。

如果是采用層序遍歷就要把每一層的結果記錄之后反轉。

遞歸C++代碼如下：

/*** 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)return root;invertTree(root->left);invertTree(root->right);swap(root->left, root->right);return root;}
};

層序遍歷c++代碼如下：?

/*** 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) {//層序遍歷//建立輔助隊列queue<TreeNode*> que;//插入根節點if(root != nullptr) {que.push(root);}//初始化sizeint size = que.size();//層序遍歷while(!que.empty()){while(size--){//記錄當前頭節點TreeNode* cur_node = que.front();//彈出que.pop();//交換左右子節點swap(cur_node->left, cur_node->right);//加入當前左右節點if(cur_node->left != nullptr) que.push(cur_node->left);if(cur_node->right != nullptr) que.push(cur_node->right);}//更新sizesize = que.size();}//return root;}
};

2.Leetcode101: 對稱二叉樹

題目鏈接：101. 對稱二叉樹 - 力扣（LeetCode）

題目解析

? ? ? ?首先就是一個誤區就可能會默認把root的情況作為中止條件，那么不難發現，這樣就可能需要回溯再比較節點的信息，實際上并沒有這么復雜，依托示例給出的三層樹就可以發現可以利用子節點的狀態來分別檢查左右兩棵子樹的信息，進而可以比較是否相同。

遞歸C++代碼如下：?

/*** 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 dfs(TreeNode* left, TreeNode* right) {if (left == nullptr && right == nullptr)return true;if (left != nullptr && right != nullptr && left->val == right->val) {// dfs(left->left, right->right);// dfs(left->right, right->left);return (dfs(left->left, right->right) &&dfs(left->right, right->left));}return false;}bool isSymmetric(TreeNode* root) {if (!root)return true;return dfs(root->left, root->right);}
};

/*** 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 isSame(TreeNode* left, TreeNode* right){if(!left&&!right)return true;else if(!left||!right) return false;else if(left->val != right->val) return false;else {//檢查外層bool outside = isSame(left->left, right->right);//檢查內層bool inside = isSame(left->right, right->left);return outside&&inside;}}bool isSymmetric(TreeNode* root) {return isSame(root->left, root->right);}
};

3.Leetcode100:相同的樹?

題目鏈接：100. 相同的樹 - 力扣（LeetCode）

題目解析

? ? ? ?101和572的思路和上面的題目的思路非常相近，細節處理不同罷了

遞歸C++代碼如下：?

/*** 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) {if(!p && !q) return true;else if(!p || !q) return false;else if(p->val != q->val) return false;//isSameTree(p->left, q->left);//isSameTree(p->right, q->right);else return bool(isSameTree(p->left, q->left)&&isSameTree(p->right, q->right));}
};

4.Leetcode572:另一棵樹的子樹?

題目鏈接：572. 另一棵樹的子樹 - 力扣（LeetCode）

題目解析

? ? ? ?101和572的思路和上面的題目的思路非常相近，細節處理不同罷了

遞歸C++代碼如下：?

/*** 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* root, TreeNode* subRoot) {if (!root && !subRoot)return true;else if (!root || !subRoot)return false;else if (root && root->val == subRoot->val)return (isSametree(root->left, subRoot->left) &&isSametree(root->right, subRoot->right));elsereturn false;}bool isSubtree(TreeNode* root, TreeNode* subRoot) {if (!root)return false;if (isSametree(root, subRoot))return true;return isSubtree(root->left, subRoot) ||isSubtree(root->right, subRoot);}
};

5.Leetcode104: 二叉樹的最大深度

題目鏈接：104. 二叉樹的最大深度 - 力扣（LeetCode）

題目解析

? ? ? ?把問題歸結為最小單元，一層的二叉樹，層數為一，最大深度為一；兩層的二叉樹，有左節點，沒有右節點，最大深度為2......那么其實遞推的過程就是在看左右最大路徑然后返回這個值。

層序迭代C++代碼如下：

/*** 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) {// 建立輔助隊列queue<TreeNode*> que;// 初始化層數int count = 0;// 插入根節點if (root != nullptr) {que.push(root);}// 初始化sizeint size = que.size();// 層序遍歷求取層數while (!que.empty()) {while (size--) {// 保存頭節點信息TreeNode* cur_node = que.front();// 彈出頭節點que.pop();// 加入彈出節點的左右子節點if (cur_node->left != nullptr)que.push(cur_node->left);if (cur_node->right != nullptr)que.push(cur_node->right);}// 記錄層數count++;// 更新sizesize = que.size();}return count;}
};

?遞歸c++代碼如下：

/*** 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;//后序遍歷遞歸體int depth_L = maxDepth(root->left);int depth_R = maxDepth(root->right);int maxdepth = max(depth_L, depth_R) + 1;return maxdepth;}
};

?簡潔版：

/*** 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;}
};

注意點：在LeelCode中深度是按照節點數量算的，而不是邊的數量。

6.Leetcode559: N叉樹的最大深度

題目鏈接：559. N 叉樹的最大深度 - 力扣（LeetCode）

題目解析

? ? ? ?和二叉樹最大的不同就是如何把多個分支都寫出來。

遞歸C++代碼如下：

/*
// Definition for a Node.
class Node {
public:int val;vector<Node*> children;Node() {}Node(int _val) {val = _val;}Node(int _val, vector<Node*> _children) {val = _val;children = _children;}
};
*/class Solution {
public:int maxDepth(Node* root) {int cur_depth = 0;if (!root)return 0;for (auto child : root->children) {cur_depth = max(cur_depth, maxDepth(child));}return cur_depth + 1;}
};