木又连续日更第94天(94/100)
木又的第138篇leetcode解题报告
二叉树
类型第28篇解题报告
leetcode第513题:找树左下角的值
https://leetcode-cn.com/problems/find-bottom-left-tree-value/
【题目】
给定一个二叉树,在树的最后一行找到最左边的值。
示例 1:
输入:
2
/ \
1 3
输出:
1
示例 2:
输入:
1
/ \
2 3
/ / \
4 5 6
/
7
输出:
7
注意: 您可以假设树(即给定的根节点)不为 NULL。
【思路】
有两个想法:一是层次遍历,记录最左边的值val,每新遍历一层,更改val的值,直到结束,返回val;二是中序遍历,记录最深层的节点值val,遍历时当节点深度更大时,替换val的值。
【代码】
python版本
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def findBottomLeftValue(self, root):
"""
:type root: TreeNode
:rtype: int
"""
# 层次遍历,找最左边的值
# 中序遍历,找最深一层最左边的节点
self.val = root.val
self.depth = 1
self.helper(root, 1)
return self.val
def helper(self, node, depth):
if not node:
return
self.helper(node.left, depth+1)
if depth > self.depth:
self.val = node.val
self.depth = depth
self.helper(node.right, depth+1)
C++版本
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int findBottomLeftValue(TreeNode* root) {
int val = root->val;
int max_depth = 1;
helper(root, 1, val, max_depth);
return val;
}
void helper(TreeNode* node, int depth, int& val, int& max_depth){
if(!node)
return ;
helper(node->left, depth+1, val, max_depth);
if(depth > max_depth){
max_depth = depth;
val = node->val;
}
helper(node->right, depth+1, val, max_depth);
}
};