226.翻轉二叉樹 （優先掌握遞歸）
題目鏈接/文章講解/視頻講解：翻轉二叉樹
交換的是指針，而不是數值，如果用數值做交換，需要交換的節點下面無法很好的操作。
使用遞歸來實現，但要提前清除是什么順序的遞歸（前中后）
具體操作是——每一個節點的左右孩子都翻轉一下指針
/*** 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:void f(TreeNode* root){if(root==NULL) return;swap(root->left,root->right);if(root->left!=NULL) f(root->left);//不寫返回if(root->right!=NULL) f(root->right);}TreeNode* invertTree(TreeNode* root) {//遞歸//參數與返回值（二叉樹）、遞歸結束條件、每一層的執行邏輯f(root);return root;}
};101. 對稱二叉樹 （優先掌握遞歸）
題目鏈接/文章講解/視頻講解：對稱二叉樹
/*** 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 f(TreeNode* a,TreeNode* b){// 先檢查空指針情況if (a == nullptr && b == nullptr) return true;if (a == nullptr || b == nullptr) return false;//這個本身包含兩個都為空，所以要放下面// 再檢查值是否相等（現在安全了）if (a->val != b->val) return false;return f(a->left,b->right)&&f(a->right,b->left);}bool isSymmetric(TreeNode* root) {//如果翻轉之后的二叉樹和之前一樣，則說明對//但是也有其他情況。。所以不能一味去翻轉//兩個子樹判斷是否相等（使用同樣的遍歷順序）if (root == nullptr) return true;return f(root->left,root->right);}
};深度與高度
- 二叉樹節點的深度：指從根節點到該節點的最長簡單路徑邊的條數或者節點數（取決于深度從0開始還是從1開始）
- 二叉樹節點的高度：指從該節點到葉子節點的最長簡單路徑邊的條數或者節點數（取決于高度從0開始還是從1開始）
- 使用前序求的就是深度，使用后序求的是高度。
104.二叉樹的最大深度 （優先掌握遞歸）
題目鏈接/文章講解/視頻講解： 二叉樹的最大深度
最大深度是要把節點盡可能的往下面放，也就是根節點（到葉子節點）的高度
遞歸遍歷計算其深度
/*** 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 f(TreeNode* node){//既然是算根節點到葉子節點的最長路徑的結點數，也就是根節點的高度，則用后序遍歷,返回最長的if(node==NULL) return 0;int ld = f(node->left);// 左int rd = f(node->right);// 右int depth = 1 + max(ld, rd); // 中return depth;}int maxDepth(TreeNode* root) {return f(root);}
};111.二叉樹的最小深度 （優先掌握遞歸）
和最大深度看似差不多，實則不然。
題目鏈接/文章講解/視頻講解：二叉樹的最小深度
/*** 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 f(TreeNode*node){if(node==NULL) return 0;int lm=f(node->left);int rm=f(node->right);if(node->left==NULL&& node->right != NULL) return 1 + rm;//if(node->right==NULL&& node->left != NULL) return 1 + lm;//int md=1+min(lm,rm);return md;}int minDepth(TreeNode* root) {//后序遍歷return f(root);}
};
)
