421- binary tree (226. reversed binary tree, 101. symmetric binary tree, 104. maximum depth of binary tree, 222. number of nodes of complete binary tree)

226. Flip binary tree

1、 Recursive method

class Solution {
    
public:
    TreeNode* invertTree(TreeNode* root) {
    
        if (root == nullptr)    return root;

        swap(root->left, root->right);

        invertTree(root->left);
        invertTree(root->right);
        return root;
    }
};

2、 Iterative method

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

101. Symmetric binary tree

1、 Recursive method

class Solution {
    
public:
    bool compare(TreeNode* left, TreeNode* right)
    {
    
        if (left == nullptr && right != nullptr) return false;
        else if (left != nullptr && right == nullptr)    return false;
        else if (left == nullptr && right == nullptr) return true;
        else if (left->val != right->val)    return false;
        else return compare(left->left, right->right) && compare(left->right, right->left);
    }

public:
    bool isSymmetric(TreeNode* root) {
    
        if (root == nullptr) return true;
        return compare(root->left, root->right);
    }
};

2、 Iterative method

class Solution {
    
public:
    bool isSymmetric(TreeNode* root) {
    
        if (root == NULL) return true;
        queue<TreeNode*> que;
        que.push(root->left);   //  Add the head node of the left subtree to the queue 
        que.push(root->right);  //  Add the head node of the right subtree to the queue 
        
        while (!que.empty()) {
      //  Next, we need to judge whether the two trees flip each other 
            TreeNode* leftNode = que.front(); que.pop();
            TreeNode* rightNode = que.front(); que.pop();
            if (!leftNode && !rightNode) {
      //  Left node is empty 、 The right node is empty , At this time, the description is symmetrical 
                continue;
            }

            //  The left and right nodes are not empty , Or they are not empty, but the values are different , return false
            if ((!leftNode || !rightNode || (leftNode->val != rightNode->val))) {
    
                return false;
            }
            que.push(leftNode->left);   //  Join the left node and the left child 
            que.push(rightNode->right); //  Join the right node and the right child 
            que.push(leftNode->right);  //  Join the left node and the right child 
            que.push(rightNode->left);  //  Join the right node and the left child 
        }
        return true;
    }
};

104. The maximum depth of a binary tree

1、 Recursive method

class Solution {
    
public:
    int get_depth(TreeNode* node)
    {
    
        if (node == nullptr)    return 0;
        int left_depth = get_depth(node->left);
        int right_depth = get_depth(node->right);
        int depth = 1 + std::max(left_depth, right_depth);
        return depth;
    }

public:
    int maxDepth(TreeNode* root) {
    
        return get_depth(root);
    }
};

2、 Iterative method

class Solution {
    
public:
    int maxDepth(TreeNode* root) {
    
        queue<TreeNode*> que;
        if (root)    que.push(root);
        int res = 0;

        while (!que.empty())
        {
    
            int size = que.size();
            res++;

            for (int i = 0; i < size; i++)
            {
    
                TreeNode* node = que.front();
                que.pop();

                if (node->left)  que.push(node->left);
                if (node->right)  que.push(node->right);
            }
        }
        return res;
    }
};

222. The number of nodes in a complete binary tree

1、 Recursive method

class Solution {
    
public:
    int get_nodes(TreeNode* node)
    {
    
        if (node == nullptr) return 0;
        int left_nodes = get_nodes(node->left);
        int right_nodes = get_nodes(node->right);
        int nodes = 1 + left_nodes + right_nodes;
        return nodes;
    }

public:
    int countNodes(TreeNode* root) {
    
        return get_nodes(root);
    }
};

2、 Iterative method

class Solution {
    
public:
    int countNodes(TreeNode* root) {
    
        queue<TreeNode*> que;
        if(root)    que.push(root);

        int res = 0;

        while(!que.empty())
        {
    
            int size = que.size();
            for(int i = 0; i < size; i++)
            {
    
                res++;
                TreeNode* node = que.front();
                que.pop();

                if(node->left)  que.push(node->left);
                if(node->right) que.push(node->right);
            }
        }
        return res;
    }
};