## Wednesday, February 15, 2017

### LeetCode OJ - Find Bottom Left Tree Value

Problem:

Analysis:

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.

Solution:

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 ...

Code:

#include "stdafx.h"

// https://leetcode.com/problems/find-bottom-left-tree-value/

#include "LEET_FIND_BOTTOM_LEFT_TREE_VALUE.h"
#include <map>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>

using namespace std;

namespace _LEET_FIND_BOTTOM_LEFT_TREE_VALUE
{
struct TreeNode
{
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution
{
public:
void findBottomLeftValue(TreeNode* root, int depth, int& max_layer, int& answer)
{
if (root == nullptr)
{
return;
}
findBottomLeftValue(root->left, depth + 1, max_layer, answer);
if (depth > max_layer)
{
max_layer = depth;
}
findBottomLeftValue(root->right, depth + 1, max_layer, answer);
}
int findBottomLeftValue(TreeNode* root)
{
int max_layer = -1;
}
};
};

using namespace _LEET_FIND_BOTTOM_LEFT_TREE_VALUE;

int LEET_FIND_BOTTOM_LEFT_TREE_VALUE()
{
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;
}