Wednesday, February 15, 2017

LeetCode OJ - Find Bottom Left Tree Value


Please find the problem here.


This problem look very much like the previous one, with a twist. We need the leftmost entry. The easiest way to make sure we get the left most entry first is simply doing an in-order traversal.


Just do an in-order traversal, keep track of the answer and update as necessary. As an aside, I hate pass by reference, that is so dangerous. I wouldn't use them in product code. But sometimes I do use it for competitive programming because it make the syntax so much simpler. A nice tool for a small problem could be a disaster used in scale ...


#include "stdafx.h"


#include <map>
#include <iostream>
#include <sstream>
#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 findBottomLeftValue(TreeNode* root, int depth, int& max_layer, int& answer)
            if (root == nullptr)
            findBottomLeftValue(root->left, depth + 1, max_layer, answer);
            if (depth > max_layer)
                max_layer = depth;
                answer = root->val;
            findBottomLeftValue(root->right, depth + 1, max_layer, answer);
        int findBottomLeftValue(TreeNode* root)
            int max_layer = -1;
            int answer = 0;
            findBottomLeftValue(root, 0, max_layer, answer);
            return answer;


    Solution solution;
    TreeNode a(2);
    TreeNode b(1);
    TreeNode c(3);
    a.left = &b;
    a.right = &c;
    cout << solution.findBottomLeftValue(&a) << endl;

    TreeNode p(1);
    TreeNode q(2);
    TreeNode r(3);
    TreeNode s(4);
    TreeNode t(5);
    TreeNode u(6);
    TreeNode v(7);
    p.left = &q;
    p.right = &r;
    q.left = &s;
    r.left = &t;
    r.right = &u;
    t.left = &v;
    cout << solution.findBottomLeftValue(&p) << endl;
    return 0;

No comments :

Post a Comment