Wednesday, February 15, 2017

LeetCode OJ - Find Largest Value in Each Tree Row

Problem:

Please find the problem here.

Analysis:

Given only the root, there is no way I can tell which subtree have the largest element in a certain row, so I have to walk the whole tree anyway. To put it more technically, suppose there exist an algorithm that does not visit all nodes, in particular, it does not visit a node p. An adversary could put a huge number in the node p and therefore the algorithm output a wrong result. Therefore any algorithm must walk the whole tree.

Solution:

Now we know we have to walk the whole tree, then the solution is relatively simple. Suppose we use a tree traversal (any traversal would do) and also keep track of the current height, then we can maintain a vector of maximum values in the current row. That would be the final result.

The interesting thing about a (just about any) tree traversal is that it increase the depth only by 1. Therefore, the vector of maximum number can increase at most by 1. That make the implementation easy by a simple push_back to the vector.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/find-largest-value-in-each-tree-row/

#include "LEET_FIND_LARGEST_VALUE_IN_EACH_TREE_ROW.h"
#include <map>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>

using namespace std;

namespace _LEET_FIND_LARGEST_VALUE_IN_EACH_TREE_ROW
{
    struct TreeNode
    {
        int val;
        TreeNode *left;
        TreeNode *right;
        TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    };
    class Solution
    {
    public:
        void largestValues(TreeNode* root, int depth, vector<int>& result)
        {
            if (root == nullptr)
            {
                return;
            }
            if (result.size() > depth)
            {
                result[depth] = max(result[depth], root->val);
            }
            else
            {
                result.push_back(root->val);
            }
            largestValues(root->left, depth + 1, result);
            largestValues(root->right, depth + 1, result);
        }
        vector<int> largestValues(TreeNode* root)
        {
            vector<int> result;
            largestValues(root, 0, result);
            return result;
        }
    };
};

using namespace _LEET_FIND_LARGEST_VALUE_IN_EACH_TREE_ROW;

int LEET_FIND_LARGEST_VALUE_IN_EACH_TREE_ROW()
{
    Solution solution;
    TreeNode a(1);
    TreeNode b(3);
    TreeNode c(2);
    TreeNode d(5);
    TreeNode e(3);
    TreeNode f(9);
    a.left = &b;
    a.right = &c;
    b.left = &d;
    b.right = &e;
    c.right = &f;
    auto result = solution.largestValues(&a);
    for (auto&& r : result)
    {
        cout << r << endl;
    }
    return 0;
}

No comments :

Post a Comment