递归法:
交换两个结点可以用swap()方法
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if(root == NULL) return NULL;
TreeNode* tem = root->left;
root->left = root->right;
root->right = tem;
invertTree(root->left);
invertTree(root->right);
return root;
}
};
迭代法:
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if(root == NULL) return NULL;
stack<TreeNode*> sta;
sta.push(root);
while(!sta.empty()) {
TreeNode* tem= sta.top();
sta.pop();
swap(tem->left, tem->right);
if(tem->right) sta.push(tem->right);
if(tem->left) sta.push(tem->left);
}
return root;
}
};
递归法:
class Solution {
public:
bool compare(TreeNode* left, TreeNode* right) {
if(left == NULL && right != NULL) {
return false;
}else if(left != NULL && right == NULL) {
return false;
}else if(left == NULL && right == NULL){
return true;
}else if (left->val != right->val) {
return false;
}
return compare(left->left, right->right) && compare(left->right, right->left);
}
bool isSymmetric(TreeNode* root) {
if(root == NULL) return true;
return compare(root->left, root->right);
}
};
递归法:
class Solution {
public:
int depth(TreeNode* root) {
if(root == NULL) return 0;
int left = depth(root->left);
int right = depth(root->right);
return left > right ? left + 1 : right + 1;
}
int maxDepth(TreeNode* root) {
if(root == NULL) return 0;
return depth(root);
}
};
迭代法:
class Solution {
public:
int maxDepth(TreeNode* root) {
if(root == NULL) return 0;
queue<TreeNode*> que;
int depth = 0;
que.push(root);
while(!que.empty()) {
int size = que.size();
depth++;
for(int i = 0; i < size; i++) {
TreeNode* tem = que.front();
que.pop();
if(tem->left) que.push(tem->left);
if(tem->right) que.push(tem->right);
}
}
return depth;
}
};
递归法:
class Solution {
public:
int depth(TreeNode* root) {
if(root->left == NULL && root->right == NULL) {
return 1;
}else if(root->left != NULL && root->right == NULL) {
return depth(root->left) + 1;
}else if(root->left == NULL && root->right != NULL) {
return depth(root->right) + 1;
}
int left = depth(root->left);
int right = depth(root->right);
return left > right ? right + 1 : left + 1;
}
int minDepth(TreeNode* root) {
if(root == NULL) return 0;
return depth(root);
}
};
迭代法:
class Solution {
public:
int minDepth(TreeNode* root) {
if(root == NULL) return 0;
queue<TreeNode*> que;
int depth = 0;
que.push(root);
while(!que.empty()) {
int size = que.size();
depth++;
for(int i = 0; i < size; i++) {
TreeNode* tem = que.front();
que.pop();
if(tem->left == NULL && tem->right == NULL) {
return depth;
}
if(tem->left) que.push(tem->left);
if(tem->right) que.push(tem->right);
}
}
return depth;
}
};