算法学习【二叉树篇】(3)

翻转二叉树

1、递归法

class Solution {
public:
  TreeNode* invertTree(TreeNode* root){
    if(root==NULL) return root;
    swap(root->left,root->right);
    invertTree(root->left);
    invertTree(root->right);
    return root;
  }
};

2、迭代法

深度优先遍历

前序遍历（写的时候中右左）

class Solution {
public:
  TreeNode* invertTree(TreeNode* root) {
    stack st;
    if(root==NULL) return root;
    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;
  }
};

后序遍历（写的时候中左右+逆）

广度优先遍历

class Solution {
public:
  TreeNode* invertTree(TreeNode* root){
    queue que;
    if(root != NULL) que.push(root);
    while(!que.empty()){
      int size = que.size();
      for(int i=0;ileft,node->right);
        if(node->left) que.push(node->left);
        if(node->right) que.push(node->right);
      }
    }
    return root;
  }
};

拓展（中序遍历特殊写法）

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (root == NULL) return root;
        invertTree(root->left);         // 左
        swap(root->left, root->right);  // 中
        invertTree(root->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 getdepth(TreeNode* node) {
        if(node==NULL) return 0;
        int leftdepth = getdepth(node->left);
        int rightdepth = getdepth(node->right);
        int depth = max(leftdepth,rightdepth)+1;
        return depth;
    }
    int maxDepth(TreeNode* root) {
        return getdepth(root);
    }
};

N叉树

class Solution {
public:
    int maxdepth(Node* node){
        if(node==NULL) return 0;
        int maxv = 0;
        vector nsize = node->children;
        for(int i=0;i

二叉树的最小深度

递归法

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

迭代法

左右子孩子都为空说明到头。

class Solution {
public:
  int maxDepth(TreeNode* root){
    if(root==NULL) return 0;
    queue que;
    que.push(root);
    int depth=0;
    if(!que.empty()){
      int size = que.size();
      depth++;
      for(int i=0;ileft) return que.push(node->left);
        if(node->right) return que.push(node->right);
        if(!node->left&&!node->right){
          return depth;
        }
      } 
    }
    return depth;
  }
};

普通二叉树的节点个数

递归法

class Solution {
public:
    int countNodes(TreeNode* root) {
        if(root==NULL){return 0;}
        return 1+countNodes(root->left)+countNodes(root->right);
    }
};

迭代法

class Solution {
public:
    int countNodes(TreeNode* root) {
      if(root==NULL){return 0;}
      queue que;
      que.push(root);
      int result=0;
      while(!que.empty()){
        int size = que.size();
        for(int i=0;ileft) que.push(node->left);
          if(node->right) que.push(node->right);
        }
      }
      return result;
    }
};

完全二叉树的节点个数

完全二叉树只有两种情况，情况一：就是满二叉树，情况二：最后一层叶子节点没有满。

对于情况一，可以直接用 2^树深度 - 1 来计算，注意这里根节点深度为1。

对于情况二，分别递归左孩子，和右孩子，递归到某一深度一定会有左孩子或者右孩子为满二叉树，然后依然可以按照情况1来计算

class Solution {
public:
    int countNodes(TreeNode* root) {
        if (root == nullptr) return 0;
        TreeNode* left = root->left;
        TreeNode* right = root->right;
        int leftHeight = 0, rightHeight = 0; // 这里初始为0是有目的的，为了下面求指数方便
        while (left) {  // 求左子树深度
            left = left->left;
            leftHeight++;
        }
        while (right) { // 求右子树深度
            right = right->right;
            rightHeight++;
        }
        if (leftHeight == rightHeight) {
            return (2 << leftHeight) - 1; // 注意(2<<1) 相当于2^2，所以leftHeight初始为0
        &#125;
        return countNodes(root->left) + countNodes(root->right) + 1;
    &#125;
&#125;;