(C++二叉树02) 翻转二叉树 对称二叉树 二叉树的深度

226、翻转二叉树

递归法：

交换两个结点可以用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;}
};

101、对称二叉树

递归法：

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);}
};

104、二叉树的最大深度

递归法：

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

111、二叉树的最小深度

递归法：

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