LeetCode - 515. Find Largest Value in Each Tree Row

Category: Algorithm
Difficulty: Medium
Tags: Tree, Depth-first Search, Breadth-first Search
Discription: https://leetcode.com/problems/find-largest-value-in-each-tree-row/#/description

本題給予一二元樹，並要求傳回各層數值最大之元素。
概念與LeetCode - 199. Binary Tree Right Side View大同小異，
先以DFS走訪各節點，再輔以記錄各層層數達成BFS之效果。
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 *     TreeNode *right;
 * };
 */
class Solution {
public:
    vector<int> largestValues(TreeNode* root) {
        vector<int> result;
        int layer = 1;
        if(root) dfs(root, result, layer);
        return result;
    }
 
    void dfs(TreeNode *root, vector<int> &result, int layer){
        // push value
        if(layer > result.size()) result.push_back(root->val);
        else result[layer-1] = max(result[layer-1], root->val);
     
        // traval left
        if(root->left) dfs(root->left, result, layer+1);
     
        // traval right
        if(root->right) dfs(root->right, result, layer+1);
    }
};

在這邊，我是以遞迴實作前序運算(Pre-Order)實作而成，
其中比較需要注意的是要記得比較各層層數，
相同層數的值要比對大小。

此外，使用堆疊實作也是沒有問題的，
如以下：
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 *     TreeNode *right;
 * };
 */
class Solution {
public:
    vector<int> largestValues(TreeNode* root) {
        vector<int> result;
        TreeNode *currNode = root;
        if(root) dfs(result, currNode);
        return result;
    }
 
    void dfs(vector<int> &result, TreeNode *currNode){
        vector<TreeNode *> stack;
        vector<int> layer_stack;
        int layer = 1;
        while(!stack.empty() || currNode){
            if(currNode){
                cout<< layer<<" "<<result.size()<<endl;
                if(layer>result.size()) result.push_back(currNode->val);
                else result[layer-1] = max(currNode->val, result[layer-1]);
             
                if(currNode->right){
                    stack.push_back(currNode->right);
                    layer_stack.push_back(layer+1);
                }
                currNode = currNode->left;
                layer++;
            }
            else{
                currNode = stack.back();
                layer = layer_stack.back();
                if(layer>result.size()) result.push_back(currNode->val);
                else result[layer-1] = max(currNode->val, result[layer-1]);
                stack.pop_back();
                layer_stack.pop_back();
                if(currNode->right){
                    stack.push_back(currNode->right);
                    layer_stack.push_back(layer+1);
                }
                currNode = currNode->left;
                layer++;
            }
        }
    }
};不過這支程式我並沒有優化的很好，
計算速度並沒有比遞迴快。