Brush questions with binary tree (4)

One 、 Mirror binary tree

Original binary tree

Mirror binary tree

Solution 1 : recursive ( recommend )

Use post order traversal , Exchange values from bottom to top

• First go to the leftmost node , Return when encountering empty node
• Enter the rightmost end of the subtree
• Return to parent question , Exchange the values of the two nodes of the parent problem

class Solution {
    
public:
    /** *  The class name in the code 、 Method name 、 The parameter name has been specified , Do not modify , Return the value specified by the method directly  * * * @param pRoot TreeNode class  * @return TreeNode class  */
    TreeNode* Mirror(TreeNode* pRoot) {
    
        // write code here
        if(pRoot==NULL)
            return NULL;
        TreeNode*left=Mirror(pRoot->left),
        *right=Mirror(pRoot->right);// Recursive subtree 
        pRoot->left=right;// In exchange for 
        pRoot->right=left;
        return pRoot;
    }
};

Time complexity :O(n), Access all nodes of the binary tree
Spatial complexity :O(n), The maximum depth of the recursive stack is n

Solution 2 : Stack

Stack is top-down access

• Determine if the tree is empty
• Use the auxiliary stack to traverse the binary tree , The root node is advanced
• When traversing, one element in the stack pops up each time , Stack the left and right nodes of the element node , Exchange the values of both at the same time

class Solution {
    
public:
    /** *  The class name in the code 、 Method name 、 The parameter name has been specified , Do not modify , Return the value specified by the method directly  * * * @param pRoot TreeNode class  * @return TreeNode class  */
    TreeNode* Mirror(TreeNode* pRoot) {
    
        // write code here
        if(pRoot==NULL)
            return NULL;
        stack<TreeNode*>s;
        s.push(pRoot);
        while(!s.empty())
        {
    
            TreeNode*tmp=s.top();
            s.pop();
            if(tmp->left)// The left and right child nodes are not empty 
                s.push(tmp->left);
            if(tmp->right)
                s.push(tmp->right);
            swap(tmp->left,tmp->right);// Exchange left and right systems, but 
        }
        return pRoot;
    }
};

Time complexity :O(n), Access all nodes of the binary tree
Spatial complexity :O(n), In the worst case, the stack size is n

Two 、 Determine whether it is a binary search tree

Binary search tree is that the node value of each left subtree is less than the root node , Each right subtree node is larger than the root node , The middle order traversal is the increasing order

Solution 1 : recursive ( recommend )

• Recursion to the leftmost , initialization pre
• Traverse the whole binary tree , Connect pre With the current node , And update the pre
• If the left subtree is not a binary search tree, it returns false
• Judge whether the current node is smaller than the previous node , Update predecessor
• Finally, it is determined by the following nodes of the right subtree

class Solution {
    
public:
    /** *  The class name in the code 、 Method name 、 The parameter name has been specified , Do not modify , Return the value specified by the method directly  * * * @param root TreeNode class  * @return bool Boolean type  */
    long pre=INT_MIN;
    bool isValidBST(TreeNode* root) {
    
        // write code here
        if(root==NULL)
            return true;
        if(!isValidBST(root->left))// First left subtree 
            return false;
        if(root->val<=pre)
            return false;
        pre=root->val;// Update node values 
        if(!isValidBST(root->right))// Then enter the right subtree 
            return false;
        return true;
    }
};

Time complexity :O(n),n Is the number of binary tree nodes , Traverse the entire binary tree
Spatial complexity :O(n), In the worst case, the binary tree degenerates into a linked list , The recursive stack depth is n

Solution 2 : Non recursive

• First judge whether the tree is empty
• Prepare an array to record the result of the sequence traversal
• Create auxiliary stack , Stop accessing when the binary tree node is empty and there is no node in the stack
• Start at the root node , First enter the leftmost node of each subtree , Add it to the stack , Save parent question
• Reach the far left rear , You can start accessing , If there is still a right node , Then the right node is stacked , The access of its right subtree is also given priority to the leftmost
• Traversal array , Compare whether the adjacent two elements are in ascending order

class Solution {
    
public:
    /** *  The class name in the code 、 Method name 、 The parameter name has been specified , Do not modify , Return the value specified by the method directly  * * * @param root TreeNode class  * @return bool Boolean type  */
    bool isValidBST(TreeNode* root) {
    
        // write code here
        stack<TreeNode*>s;
        TreeNode*head=root;
        vector<int>v;
        while(head!=NULL||!s.empty())
        {
    
            while(head!=NULL)// Until there is no left node 
            {
    
                s.push(head);
                head=head->left;
            }
            head=s.top();
            s.pop();
            v.push_back(head->val);
            head=head->right;
        }
        for(int i=1;i<v.size();i++)
        {
    
            if(v[i-1]>v[i])// Existence descending order , It's not a search tree 
                return false;
        }
        return true;
    }
};

Time complexity :O(n), Number of binary tree nodes n
Spatial complexity :O(n), Auxiliary stack and auxiliary space

3、 ... and 、 Determine whether it is a complete binary tree

A complete binary tree means that leaf nodes can only appear at the lowest or secondary level

Level traversal ( recommend )

• Priority to determine whether the tree is empty
• Initialize a queue auxiliary level traversal , Add the root node to the queue
• Pop the node from the queue , If a node is empty , marked , If you can visit later , It means that leaf nodes appear in advance
• otherwise , Continue to join the left and right child nodes and enter the queue

class Solution {
    
public:
    /** *  The class name in the code 、 Method name 、 The parameter name has been specified , Do not modify , Return the value specified by the method directly  * * * @param root TreeNode class  * @return bool Boolean type  */
    bool isCompleteTree(TreeNode* root) {
    
        // write code here
        if(root==NULL)
            return true;
        queue<TreeNode*>q;
        q.push(root);
        bool flag=false;
        while(!q.empty())
        {
    
           int n=q.size();
            for(int i=0;i<n;i++)
            {
    
                TreeNode*node=q.front();
                q.pop();
                if(node==NULL)// The tag encounters an empty node for the first time 
                    flag=true;
                else// Empty node has been encountered in subsequent access , It means passing through the leaves , If there are non empty nodes , Go straight back to false
                {
    
                    if(flag)
                        return false;
                    q.push(node->left);
                    q.push(node->right);
                }
            }
        }
        return true;
    }
};

Time complexity ：O(n), among n Is the number of binary tree nodes , Hierarchical traversal worst case traversal of each node
Spatial complexity ：O(n), In the worst case , The maximum space of the hierarchical queue is O(n)

Four 、 Determine whether it is a balanced binary tree

The difference in the depth of subtrees on both sides of any node of the balanced binary tree is no more than 1

Solution 1 : The top-down

• Create the first function to recursively traverse all nodes of the binary tree
• Call the second function for each node to get the subtree depth
• The subtree depth acquisition function created , Just traverse down the depth , Accumulate the larger values of the left and right depths
• Judge whether it is a horizontal binary tree according to the depth

class Solution {
    
public:
    int depth(TreeNode*root)
    {
    
        if(root==NULL)
            return 0;
        int left=depth(root->left),// Recursively calculate the depth of left and right subtrees 
        right=depth(root->right);
        return max(left,right)+1;// Taking the maximum +1
    }
    bool IsBalanced_Solution(TreeNode* pRoot) {
    
        if(pRoot==NULL)
            return true;
        int left=depth(pRoot->left),
        right=depth(pRoot->right);
        if(abs(left-right)>1)// If the depth difference is greater than one, it is not a balanced tree 
            return false;
        return IsBalanced_Solution(pRoot->left)&&IsBalanced_Solution(pRoot->right);
        // Recursively judge the left and right subtrees 
    }
};

Time complexity :O(n^2), The deepest two recursions are n
Spatial complexity :O(n), Maximum depth of recursive stack

Solution 2 : Bottom up ( recommend )

There are disadvantages from the top up , Time complexity is high , From bottom to top, depth calculation and judgment can be completed at the same time

• First judge the empty tree
• Recursively calculate the depth and determine whether it is a balanced binary tree
• Recursively calculate the height difference between the left and right subtrees of the current node , More depth
• Each recursion returns the depth result , You can calculate the depth while judging

class Solution {
    
public:
    bool Judge(TreeNode*root,int&depth)
    {
    
        if(root==NULL)
        {
    
            depth=0;
            return true;
        }
        int left=0,right=0;
        if(Judge(root->left, left)==false||
           Judge(root->right, right)==false)// Left and right subtrees judge 
            return false;
        if(abs(left-right)>1)// Judge 
            return false;
        depth=max(left,right)+1;
        return true;
    }
    bool IsBalanced_Solution(TreeNode* pRoot) {
    
        int depth=0;
        return Judge(pRoot,depth);
    }
};

Time complexity :O(n), recursive n Nodes
Spatial complexity :O(n), Recursive stack depth