当前位置:   article > 正文

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

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

226、翻转二叉树

递归法:

交换两个结点可以用swap()方法

  1. class Solution {
  2. public:
  3. TreeNode* invertTree(TreeNode* root) {
  4. if(root == NULL) return NULL;
  5. TreeNode* tem = root->left;
  6. root->left = root->right;
  7. root->right = tem;
  8. invertTree(root->left);
  9. invertTree(root->right);
  10. return root;
  11. }
  12. };

迭代法:

  1. class Solution {
  2. public:
  3. TreeNode* invertTree(TreeNode* root) {
  4. if(root == NULL) return NULL;
  5. stack<TreeNode*> sta;
  6. sta.push(root);
  7. while(!sta.empty()) {
  8. TreeNode* tem= sta.top();
  9. sta.pop();
  10. swap(tem->left, tem->right);
  11. if(tem->right) sta.push(tem->right);
  12. if(tem->left) sta.push(tem->left);
  13. }
  14. return root;
  15. }
  16. };

101、对称二叉树

递归法:

  1. class Solution {
  2. public:
  3. bool compare(TreeNode* left, TreeNode* right) {
  4. if(left == NULL && right != NULL) {
  5. return false;
  6. }else if(left != NULL && right == NULL) {
  7. return false;
  8. }else if(left == NULL && right == NULL){
  9. return true;
  10. }else if (left->val != right->val) {
  11. return false;
  12. }
  13. return compare(left->left, right->right) && compare(left->right, right->left);
  14. }
  15. bool isSymmetric(TreeNode* root) {
  16. if(root == NULL) return true;
  17. return compare(root->left, root->right);
  18. }
  19. };

104、二叉树的最大深度

递归法:

  1. class Solution {
  2. public:
  3. int depth(TreeNode* root) {
  4. if(root == NULL) return 0;
  5. int left = depth(root->left);
  6. int right = depth(root->right);
  7. return left > right ? left + 1 : right + 1;
  8. }
  9. int maxDepth(TreeNode* root) {
  10. if(root == NULL) return 0;
  11. return depth(root);
  12. }
  13. };

迭代法:

  1. class Solution {
  2. public:
  3. int maxDepth(TreeNode* root) {
  4. if(root == NULL) return 0;
  5. queue<TreeNode*> que;
  6. int depth = 0;
  7. que.push(root);
  8. while(!que.empty()) {
  9. int size = que.size();
  10. depth++;
  11. for(int i = 0; i < size; i++) {
  12. TreeNode* tem = que.front();
  13. que.pop();
  14. if(tem->left) que.push(tem->left);
  15. if(tem->right) que.push(tem->right);
  16. }
  17. }
  18. return depth;
  19. }
  20. };

111、二叉树的最小深度

递归法:

  1. class Solution {
  2. public:
  3. int depth(TreeNode* root) {
  4. if(root->left == NULL && root->right == NULL) {
  5. return 1;
  6. }else if(root->left != NULL && root->right == NULL) {
  7. return depth(root->left) + 1;
  8. }else if(root->left == NULL && root->right != NULL) {
  9. return depth(root->right) + 1;
  10. }
  11. int left = depth(root->left);
  12. int right = depth(root->right);
  13. return left > right ? right + 1 : left + 1;
  14. }
  15. int minDepth(TreeNode* root) {
  16. if(root == NULL) return 0;
  17. return depth(root);
  18. }
  19. };

迭代法:

  1. class Solution {
  2. public:
  3. int minDepth(TreeNode* root) {
  4. if(root == NULL) return 0;
  5. queue<TreeNode*> que;
  6. int depth = 0;
  7. que.push(root);
  8. while(!que.empty()) {
  9. int size = que.size();
  10. depth++;
  11. for(int i = 0; i < size; i++) {
  12. TreeNode* tem = que.front();
  13. que.pop();
  14. if(tem->left == NULL && tem->right == NULL) {
  15. return depth;
  16. }
  17. if(tem->left) que.push(tem->left);
  18. if(tem->right) que.push(tem->right);
  19. }
  20. }
  21. return depth;
  22. }
  23. };

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/笔触狂放9/article/detail/846022
推荐阅读
相关标签
  

闽ICP备14008679号