515. Find Largest Value in Each Tree Row

class Solution 
{
private:
    int maxDepth = -1;
    vector<int> largestValueAtLevel = vector<int>(10000, INT_MIN);
    // if we use map, we have to judge whether the key is existed, I don't know its time complexity
    // but if we use vector, it will take up O(n) space complexity, while the recursion will also take O(n)
    // so it will not affect the whole spave complexity
    
    void preorderTraverse(TreeNode *i_root, int depth)
    {
        maxDepth = max(maxDepth, depth);
        largestValueAtLevel[depth] = max(largestValueAtLevel[depth], i_root->val);
        
        if(i_root->left) preorderTraverse(i_root->left, depth + 1);
        if(i_root->right) preorderTraverse(i_root->right, depth + 1);
    } 
public:
    // vector<int> largestValues(TreeNode* root)
    vector<int> largestValues(TreeNode *i_root) 
    {
        if(!i_root) return vector<int>{};
        
        preorderTraverse(i_root, 0);
        
        vector<int> result(maxDepth + 1);
        for(int i = 0; i <= maxDepth; i++)
        {
            result[i] = largestValueAtLevel[i];
        }
        
        return result;
    }
};

class Solution 
{
public:
    // vector<int> largestValues(TreeNode* root)
    vector<int> largestValues(TreeNode *i_root) 
    {
        if(!i_root) return vector<int>{};
        
        vector<int> result; 
        queue<const TreeNode *> currentLevelNodes{{i_root}};
        queue<const TreeNode *> nextLevelNodes;
        
        int maxLevelValue = INT_MIN;
        while(!currentLevelNodes.empty() || !nextLevelNodes.empty())
        {
            if(currentLevelNodes.empty())
            {                       
                swap(currentLevelNodes, nextLevelNodes);  
                result.push_back(maxLevelValue);
                
                maxLevelValue = INT_MIN;
            }
            else
            {
                auto node = currentLevelNodes.front();
                currentLevelNodes.pop();
                
                maxLevelValue = max(maxLevelValue, node->val);
                
                if(node->left) nextLevelNodes.push(node->left);
                if(node->right) nextLevelNodes.push(node->right);
            }
        }
        
        result.push_back(maxLevelValue);
        
        return result;
    }
};

// the algorithm's space complexity is O(1), but we have use a vector to return, so we think the total space complexity is O(n)
// on the other hand, to better describe the complexity, we could ignore the required complexity like the space taken by the answer

// all iteration methords could use morris rather than recursion or level iteration
// but this methord it pretty hard
// and the time complexity is more imprtant than space complexity

// The process of Morris Traversal
// 1. if current node doesn't have a left child, go right
// 2. if current node have a left child, find its most right node
//      3.1 if the most right node's right pointer is nullptr, let it point to the current node and go left
//      3.2 if the most right node's right pointer points to the current node, let it be nullptr and go right

// case 3.1 and 3.2 actually means whether or not we have iterated the left node
// the reason why we find the left child's most right node is in the preorder, the next node of that one is the current node
// so this is a methord to return back to the parent node without using a stack

class Solution 
{
public:
    // vector<int> largestValues(TreeNode* root)
    vector<int> largestValues(TreeNode *i_root) 
    {
        vector<int> result;
        TreeNode *currentNode = i_root, *previousNode = nullptr;
        int depth = 0;
        while(currentNode)
        {
            if(!currentNode->left) // case 1, go left
            {
                if(depth >= result.size()) result.push_back(currentNode->val);
                else result[depth] = max(result[depth], currentNode->val);
                
                depth++;
                currentNode = currentNode->right;
            }
            else 
            {
                previousNode = currentNode->left; // case 2, let previousNode be currentNode->left, then find the most right node
                
                int moveSteps = 1;
                while(previousNode->right && previousNode->right != currentNode)
                {
                    previousNode = previousNode->right;
                    moveSteps++;
                }
                
                if(!previousNode->right)
                {
                    if(depth >= result.size()) result.push_back(currentNode->val);
                    
                    previousNode->right = currentNode;
                    currentNode = currentNode->left;
                    depth++;
                }
                else
                {
                    previousNode->right = nullptr;
                    depth -= moveSteps + 1;
                    
                    if(depth >= result.size()) result.push_back(currentNode->val);
                    else result[depth] = max(result[depth], currentNode->val);
                    
                    currentNode = currentNode->right;
                    depth++;
                }
            }
        }
        
        return result;
    }
};