One 、 Print binary trees in zigzag order

Solution 1 : Non recursive ( recommend )

• First judge whether the binary tree is empty
• Establish a secondary queue , The root node is queued first , Because no matter how you visit , The root node must be the first , In front of the queue , Set the print order marking amount flag, Every other layer is transformed into false or true, Judge the printing order accordingly
• Every floor , Count the number of queue elements , change flag A variable's value , The number of elements in the current queue is the number of nodes in this layer
• After traversing one layer , Pop it out of the queue , Into a one-dimensional array , If there are child nodes , Join the queue for the next level of operation
• according to flag Variable determination is to directly add a one-dimensional array to a two-dimensional array , Or reverse and then add
  This problem adds a flag Judge

class Solution {
    
public:
    vector<vector<int> > Print(TreeNode* pRoot) {
    
        TreeNode*cur=pRoot,*p;
        vector<vector<int>>v;
        if(cur==NULL)
            return v;
        queue<TreeNode*>q;
        q.push(cur);// First line in 
        bool flag=true;
        while(!q.empty())
        {
    
            vector<int>tmp;
            int n=q.size();
            flag=!flag;// Odd row inversion , Even lines do not reverse 
            for(int i=0;i<n;i++)
            {
    
                p=q.front();
                q.pop();
                tmp.push_back(p->val);
                if(p->left)
                    q.push(p->left);
                if(p->right)
                    q.push(p->right);
            }
            if(flag)// Odd row inversion , Even lines do not reverse 
                reverse(tmp.begin(),tmp.end());
            v.push_back(tmp);
        }
        return v;
    }
    
};

Time complexity :O(n),reverse The time complexity is O(n), Loop traversal n Nodes
Spatial complexity :O(n), Queue space n

Solution 2 : recursive

Set the inversion function on the basis of recursive traversal of sequence
The first one is from left to right , the second , From right to left , Every other one is the same
Because a single recursion cannot store all nodes , The reverse order must be completed after recursion , After the node is stored

class Solution {
    
public:
    void change(vector<vector<int>>&v)
    {
    
        for(int i=0;i<v.size();i++)
        {
    
            if(i%2)// Odd numbers in reverse order 
               reverse(v[i].begin(),v[i].end());
        }
    }
    void _levelorder(vector<vector<int>>&v,TreeNode*root,int depth)
    {
    
       if(root)
       {
    
          if(v.size()<depth)
              v.push_back(vector<int>{
    });
          v[depth-1].push_back(root->val);
       }
        else
            return ;
        _levelorder(v, root->left, depth+1);
        _levelorder(v, root->right, depth+1);
        
    }
    vector<vector<int> > Print(TreeNode* pRoot) {
    
        vector<vector<int>>v;
        if(pRoot==NULL)
            return v;
        _levelorder(v, pRoot, 1);
        change(v);
        return v;
    }
};

Time complexity :O(n),reverse Spatial complexity O(n), Recursively traverse nodes
Spatial complexity :O(n), The maximum depth of the recursive stack is n

Solution 3 : Double stack method

• Create two auxiliary stacks , Visit each time in turn s1,s2 These two stacks
• According to the order ,s1 Must record odd layers , Then its child nodes enter in the order from left to right s2 Stack , When it comes out of the stack, it is in reverse order ,s2 Even layers , Its child nodes will enter in the order from right to left s1 Stack , The stack is positive , Thus cycle
• After each visit , That is, when a stack is empty , Add a one-dimensional array to a two-dimensional array

class Solution {
    
public:
    vector<vector<int> > Print(TreeNode* pRoot) {
    
        TreeNode*cur=pRoot;
        vector<vector<int>>v;
        if(cur==NULL)
            return v;
        stack<TreeNode*>s1,s2;
        s1.push(cur);// first floor 
        while(!s1.empty()||!s2.empty())
        {
    
             vector<int>tmp;
             while(!s1.empty())// Traverse odd layers 
             {
    
                 TreeNode*node=s1.top();
                 s1.pop();
                 tmp.push_back(node->val);
                 if(node->left)
                     s2.push(node->left);// Child nodes join even layers , Stack positive order , Reverse the order when leaving the stack 
                 if(node->right)
                     s2.push(node->right);
             }
            if(tmp.size())
                v.push_back(tmp);
            tmp.clear();
             while(!s2.empty())
             {
    
                 TreeNode*node=s2.top();
                 s2.pop();
                 tmp.push_back(node->val);
                 if(node->right)// Pay attention to the change of adding order , Stack in reverse order , Positive order when leaving the stack 
                     s1.push(node->right);
                 if(node->left)
                     s1.push(node->left);
             }
             if(tmp.size())
                v.push_back(tmp);
        }
        return v;
    }
};

Time complexity :O(n), Traverse all nodes of the binary tree
Spatial complexity :O(n), The worst case of space between two stacks is n

Two 、 The maximum depth of a binary tree

Depth refers to the number of nodes on the path from the root node of the tree to any leaf node , Each time the root node goes down one layer, the depth will deepen 1, Thus, the depth of the binary tree is equal to the maximum value of one layer of the root node plus the depth of the left and right subtrees

Solution 1 : recursive ( recommend )

• Keep going down, that is, the child node recurses until it is empty
• Recursively reverse the maximum value of the subtrees on both sides plus the depth of this level , The add 1
• Each level of task is to find its depth for entering the left and right subtrees

class Solution {
    
public:
    /** * * @param root TreeNode class  * @return int integer  */
    
    int maxDepth(TreeNode* root) {
    
        // write code here
        if(root==NULL)
            return 0;
        return max(maxDepth(root->left),maxDepth(root->right))+1;// Take the maximum node value plus 1
    }
};

Time complexity :O(n), 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 : Level traversal

According to sequence traversal , Remove the stored value operation here , Keep the depth

• Use queues to record nodes of each layer
• When traversing each layer , First count the number of this layer , Then traverse the corresponding nodes
• After traversing and playing one layer , Depth plus one

class Solution {
    
public:
    /** * * @param root TreeNode class  * @return int integer  */
    int maxDepth(TreeNode* root) {
    
        // write code here
        if(root==NULL)
            return 0;
        queue<TreeNode*>q;
        q.push(root);
        int depth=0;
        while(!q.empty())
        {
    
            int n=q.size();// First record the number of nodes in the current layer 
            for(int i=0;i<n;i++)// After traversing this layer, go to the next layer 
            {
    
                TreeNode*node=q.front();
                q.pop();
                if(node->left)
                    q.push(node->left);
                if(node->right)
                    q.push(node->right);
            }
            depth++;
        }
        return depth;
    }
};

Time complexity :O(n), Traverse the entire binary tree
Spatial complexity :O(n), The maximum auxiliary queue space is n

3、 ... and 、 The path of a value in a binary tree ( One )

The topic requires that nodes can only be from top to bottom

Solution 1 : recursive ( recommend )

• Recursive preorder traversal
• Check whether the node is empty every time
• Check whether the traversal node is a leaf node , And when the current sum Found when the value is equal to the node value
• Check whether the left and right nodes have a path that can be completed , As long as there is one, it is true, So we use || Judge

class Solution {
    
public:
    /** * * @param root TreeNode class  * @param sum int integer  * @return bool Boolean type  */
    bool hasPathSum(TreeNode* root, int sum) {
    
        // write code here
        if(root==NULL)
            return false;
        if(root->left==NULL&&root->right==NULL&&root->val==sum)// When there are no child nodes and sum When the value is reduced to equal to the value of this node , Path exists 
            return true;
        return hasPathSum(root->left, sum-root->val)||hasPathSum(root->right, sum-root->val);// There is at least one path to the left and right 
    }
};

Time complexity :O(n), 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

Use stack assist , Conduct dfs Traverse

• Check the empty node
• Use two stacks to traverse synchronously , A record node , Auxiliary depth first search , Another stack records the path and... So far , Yes c++, Then use a stack , utilize pair Record two sets of data for the Group , The root node is put on the stack first
• If there is no leaf node, put the left and right child nodes on the stack , And add path and

class Solution {
    
public:
    /** * * @param root TreeNode class  * @param sum int integer  * @return bool Boolean type  */
    bool hasPathSum(TreeNode* root, int sum) {
    
        // write code here
        if(root==NULL)
            return false;
        stack<pair<TreeNode*,int>>s;// Pair up , Storage nodes and accumulated values 
        s.push({
    root,root->val});
        while(!s.empty())
        {
    
            auto tmp=s.top();
            s.pop();
            if(tmp.first->left==NULL&&tmp.first->right==NULL&&tmp.second==sum)// Left and right are empty , And the cumulative value of nodes is equal to sum, Find the way 
                return true;
            if(tmp.first->left)// When judging its left and right child nodes , Push 
                s.push({
    tmp.first->left,tmp.second+tmp.first->left->val});
            if(tmp.first->right)
                s.push({
    tmp.first->right,tmp.second+tmp.first->right->val});
        }
        return false;// After traversing, we didn't find , non-existent , For false 
    }
};

Time complexity :O(n),dfs Traverse all linked lists of the binary tree
Spatial complexity :O(n), The worst case of auxiliary stack is n