513. 找树左下角的值
中等
相关标签
相关企业
给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。
假设二叉树中至少有一个节点。
示例 1:
输入: root = [2,1,3]
输出: 1
示例 2:
输入: [1,2,3,4,null,5,6,null,null,7]
输出: 7
提示:
- 二叉树的节点个数的范围是
[1,104] -231 <= Node.val <= 231 - 1
class Solution {
public:int max_depth = INT_MIN;int result = 0;void traversal(TreeNode* node,int depth){//寻找深度最大的叶子节点，同时保证要先遍历左孩子，再遍历右孩子if(node->left==NULL && node->right==NULL){if(depth>max_depth){ //这里一定不能带等于，否则会被同深度的右边的叶子节点所覆盖result = node->val;max_depth = depth;} }//注意一定先遍历左结点，还有不要忘记回溯if(node->left){depth++;traversal(node->left,depth);depth--;}if(node->right){depth++;traversal(node->right,depth);depth--;}}int findBottomLeftValue(TreeNode* root) {traversal(root,0);return result;}
};
- 可以使用层序遍历（迭代法），非常简单，前面的题第二次做时也看看能不能用迭代法去做
- 这里重点讲递归