1、226翻转二叉树
给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
我的思路： 懵了一会儿。遍历到当前节点时，需要将它的子节点交换一下。所以需要在前序位置做交换最合适。
代码随想录：递归遍历、DFS迭代遍历（栈）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
|
class Solution {
public:
void traverse(TreeNode* root){
if(root == nullptr)return;
auto temp = root->left;
root->left = root->right;
root->right = temp;
traverse(root->left);
traverse(root->right);
}
TreeNode* invertTree(TreeNode* root) {
traverse(root);
return root;
}
};
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if (root == NULL) return root;
stack<TreeNode*> st;
st.push(root);
while(!st.empty()) {
TreeNode* node = st.top();
st.pop();
swap(node->left, node->right);
if(node->right) st.push(node->right);
if(node->left) st.push(node->left);
}
return root;
}
};
|
2、101对称二叉树
给你一个二叉树的根节点 root ， 检查它是否轴对称。
我的思路： 把树分为左子树和右子树，两棵树同时遍历比较。左子树从左到右，右子树从右到左。可以共用一个队列。我只想到层序遍历。 递归想不出来。两个子树同时递归怎么做？
代码随想录：看了代码随想录之后我发现好简单，递归函数参数多传一个节点就行。。 我觉得难点在于如何判断使用哪种递归方式（前、中、后），以及递归返回值、递归参数怎样确定。
视频
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
|
class Solution {
public:
bool isSymmetric(TreeNode* root) {
if(root == nullptr) return true;
queue<TreeNode*> pq;
pq.push(root->left);
pq.push(root->right);
while(!pq.empty()){
auto left = pq.front();
pq.pop();
auto right = pq.front();
pq.pop();
if(left == nullptr && right!=nullptr)return false;
if(left != nullptr && right==nullptr)return false;
if(left == nullptr && right == nullptr)continue;
if(left->val != right->val)return false;
pq.push(left->left);
pq.push(right->right);
pq.push(left->right);
pq.push(right->left);
}
return true;
}
};
class Solution {
public:
bool traverse(TreeNode* tl,TreeNode* tr){
if(tl == nullptr && tr!=nullptr)return false;
if(tl != nullptr && tr==nullptr)return false;
if(tl == nullptr && tr==nullptr)return true;
if(tl->val != tr->val)return false;
bool out = traverse(tl->left,tr->right);
bool in = traverse(tl->right,tr->left);
return out && in;
}
bool isSymmetric(TreeNode* root) {
if(root == nullptr) return true;
return traverse(root->left,root->right);
}
};
|
3、104二叉树的最大深度（递归解法）
我的思路： 这道题用递归解法来解。我把depth和max_depth作为递归函数参数。我感觉我对递归函数返回值怎样设计一窍不通，导致很多变量我都放在参数里，没有返回值就意味着基本都是前序遍历。
我的小思考：前序就是从上往下递归，后序就是从下往上收拢，所以后序一般用于返回值
代码随想录：
- 确定递归函数的参数和返回值：参数就是传入树的根节点，返回就返回这棵树的深度，所以返回值为int类型。
- 确定终止条件：如果为空节点的话，就返回0，表示高度为0。
- 确定单层递归的逻辑：先求它的左子树的深度，再求右子树的深度，最后取左右深度最大的数值 再+1 （加1是因为算上当前中间节点）就是目前节点为根节点的树的深度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
|
class Solution {
public:
void traverse(TreeNode* root, int depth, int &max_depth){
if(root==nullptr)return;
if(depth > max_depth){
max_depth = depth;
}
traverse(root->left,depth+1,max_depth);
traverse(root->right,depth+1,max_depth);
}
int maxDepth(TreeNode* root) {
if(root == nullptr)return 0;
int depth = 1;
int max_depth = 0;
traverse(root,depth,max_depth);
return max_depth;
}
};
class Solution {
public:
int traverse(TreeNode* root){
if(root==nullptr)return 0;
int left_depth = traverse(root->left);
int right_depth = traverse(root->right);
return 1+std::max(left_depth,right_depth);
}
int maxDepth(TreeNode* root) {
if(root == nullptr)return 0;
return traverse(root);
}
};
|
4、111二叉树的最小深度（递归解法）
我的思路： 受上一题的启发 --> 递归最终的结果作为返回值，主要是找到截止条件。二叉树的遍历一般是判断当前指针是否为nullptr截止，但是最小深度需要判断子节点的全部是否为nullptr。
代码随想录：和我的思路一样，写的没我的绕。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
|
class Solution {
public:
int traverse(TreeNode* root){
if(root->left==nullptr && root->right==nullptr)return 1;
int left_depth = 9999999;
int right_depth = 9999999;
if(root->left != nullptr){
left_depth = traverse(root->left);
}
if(root->right != nullptr){
right_depth = traverse(root->right);
}
return 1+std::min(left_depth,right_depth);
}
int minDepth(TreeNode* root) {
if(root == nullptr)return 0;
return traverse(root);
}
};
class Solution {
public:
int getDepth(TreeNode* node) {
if (node == NULL) return 0;
int leftDepth = getDepth(node->left);
int rightDepth = getDepth(node->right);
if (node->left == NULL && node->right != NULL) {
return 1 + rightDepth;
}
if (node->left != NULL && node->right == NULL) {
return 1 + leftDepth;
}
int result = 1 + min(leftDepth, rightDepth);
return result;
}
int minDepth(TreeNode* root) {
return getDepth(root);
}
};
|
代码随想录算法训练第十四天|226翻转二叉树(递归)|101对称二叉树(递归)|104二叉树的最大深度(递归)|111二叉树的最小深度(递归)
