513. Find Bottom Left Tree Value (Medium)

Given the root of a binary tree, return the leftmost value in the last row of the tree.

 

Example 1:

Input: root = [2,1,3]
Output: 1

Example 2:

Input: root = [1,2,3,4,null,5,6,null,null,7]
Output: 7

 

Constraints:

• The number of nodes in the tree is in the range [1, 104].
• -231 <= Node.val <= 231 - 1

A:

递归， 找出高度，然后对比看看左子树的是不是这个高度。 

如果是，则只需要看左子树。否则看右子树

/**

* Definition for a binary tree node.

* struct TreeNode {

* int val;

* TreeNode *left;

* TreeNode *right;

* TreeNode() : val(0), left(nullptr), right(nullptr) {}

* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}

* };

*/

class Solution {

public:

int findBottomLeftValue(TreeNode* root) {

return helper(root, getHeight(root));

}

private:

int helper(TreeNode* root, int height){

if(height == 1)

return root->val;

int leftHeight = getHeight(root->left);

if(leftHeight == height -1){

return helper(root->left, height-1);

}else{

return helper(root->right, height-1);

}

}

int getHeight(TreeNode* root){

if(!root)

return 0;

return 1 + max(getHeight(root->left), getHeight(root->right));

}

};

但是上面的解法time 效率不好

************下面是 迭代解法。 beat 100%***************

class Solution {

public:

int findBottomLeftValue(TreeNode* root) {

vector<TreeNode*> V{root};

int idx = 0;

while(idx < V.size()){

if(V[idx]->right){

V.push_back(V[idx]->right);

}

if(V[idx]->left){

V.push_back(V[idx]->left);

}

idx++;

}

return V.back()->val;

}

};