[leetcode] 513. Find Bottom Left Tree Value

[leetcode] 513. Find Bottom Left Tree Value

Description

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

Example 1:

Input: 2 / \ 1 3Output:1

Example 2:

Input: 1 / \ 2 3 / / \ 4 5 6 / 7Output:7

Note: You may assume the tree (i.e., the given root node) is not NULL.

分析

题目的意思是：求一棵二叉树中最后一行，最左边的叶子结点。

树的问题就是递归，然后是先序遍历，由于先序遍历遍历的顺序是根-左-右，所以每一行最左边的结点肯定最先遍历到，那么由于是新一行，那么当前深度肯定比之前的最大深度大，所以我们可以更新最大深度为当前深度，结点值res为当前结点值，这样在遍历到该行其他结点时就不会更新结果res了。

代码

/** * 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 res; int mx=0; int cnt=1; solve(root,mx,cnt,res); return res; } void solve(TreeNode* root,int& mx,int cnt,int& res){ if(!root){ return; } if(cnt>mx){ mx=cnt; res=root->val; } solve(root->left,mx,cnt+1,res); solve(root->right,mx,cnt+1,res); }};

参考文献

​​[LeetCode] Find Bottom Left Tree Value 寻找最左下树结点的值​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。