Wednesday, February 15, 2017

LeetCode OJ - Find Largest Value in Each Tree Row


Please find the problem here.


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.


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.


#include "stdafx.h"


#include <map>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>

using namespace std;

    struct TreeNode
        int val;
        TreeNode *left;
        TreeNode *right;
        TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    class Solution
        void largestValues(TreeNode* root, int depth, vector<int>& result)
            if (root == nullptr)
            if (result.size() > depth)
                result[depth] = max(result[depth], 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;


    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