513.find-bottom-left-tree-value.md

题目地址（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 

BFS

思路

其实问题本身就告诉你怎么做了

在树的最后一行找到最左边的值。

问题再分解一下

• 找到树的最后一行
• 找到那一行的第一个节点

不用层序遍历简直对不起这个问题，这里贴一下层序遍历的流程

令curLevel为第一层节点也就是root节点 定义nextLevel为下层节点 遍历node in curLevel, nextLevel.push(node.left) nextLevel.push(node.right) 令curLevel = nextLevel, 重复以上流程直到curLevel为空 

代码

• 代码支持：JS，Python，Java，CPP, Go, PHP

JS Code：

varfindBottomLeftValue=function(root){letcurLevel=[root];letres=root.val;while(curLevel.length){letnextLevel=[];for(leti=0;i<curLevel.length;i++){curLevel[i].left&&nextLevel.push(curLevel[i].left);curLevel[i].right&&nextLevel.push(curLevel[i].right);}res=curLevel[0].val;curLevel=nextLevel;}returnres;};

Python Code:

classSolution(object): deffindBottomLeftValue(self, root): queue=collections.deque() queue.append(root) whilequeue: length=len(queue) res=queue[0].valfor_inrange(length): cur=queue.popleft() ifcur.left: queue.append(cur.left) ifcur.right: queue.append(cur.right) returnres

Java：

classSolution { Map<Integer,Integer> map = newHashMap<>(); intmaxLevel = 0; publicintfindBottomLeftValue(TreeNoderoot) { if (root == null) return0; LinkedList<TreeNode> deque = newLinkedList<>(); deque.add(root); intres = 0; while(!deque.isEmpty()) { intsize = deque.size(); for (inti = 0; i < size; i++) { TreeNodenode = deque.pollFirst(); if (i == 0) { res = node.val; } if (node.left != null)deque.addLast(node.left); if (node.right != null)deque.addLast(node.right); } } returnres; } }

CPP：

classSolution { public:intfindBottomLeftValue_bfs(TreeNode* root) { queue<TreeNode*> q; TreeNode* ans = NULL; q.push(root); while (!q.empty()) { ans = q.front(); int size = q.size(); while (size--) { TreeNode* cur = q.front(); q.pop(); if (cur->left ) q.push(cur->left); if (cur->right) q.push(cur->right); } } return ans->val; } }

Go Code:

/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */funcfindBottomLeftValue(root*TreeNode) int { res:=root.ValcurLevel:= []*TreeNode{root} // 一层层遍历forlen(curLevel) >0 { res=curLevel[0].ValvarnextLevel []*TreeNodefor_, node:=rangecurLevel { ifnode.Left!=nil { nextLevel=append(nextLevel, node.Left) } ifnode.Right!=nil { nextLevel=append(nextLevel, node.Right) } } curLevel=nextLevel } returnres }

PHP Code:

/** * Definition for a binary tree node. * class TreeNode { * public $val = null; * public $left = null; * public $right = null; * function __construct($value) { $this->val = $value; } * } */class Solution { /** * @param TreeNode $root * @return Integer */functionfindBottomLeftValue($root) { $curLevel = [$root]; $res = $root->val; while (count($curLevel)) { $nextLevel = []; $res = $curLevel[0]->val; foreach ($curLevelas$node) { if ($node->left) $nextLevel[] = $node->left; if ($node->right) $nextLevel[] = $node->right; } $curLevel = $nextLevel; } return$res; } }

复杂度分析

• 时间复杂度：$O(N)$，其中 N 为树的节点数。
• 空间复杂度：$O(Q)$，其中 Q 为队列长度，最坏的情况是满二叉树，此时和 N 同阶，其中 N 为树的节点总数

DFS

思路

树的最后一行找到最左边的值，转化一下就是找第一个出现的深度最大的节点，这里用先序遍历去做，其实中序遍历也可以，只需要保证左节点在右节点前被处理即可。 具体算法为，先序遍历 root，维护一个最大深度的变量，记录每个节点的深度，如果当前节点深度比最大深度要大，则更新最大深度和结果项。

代码

代码支持：JS，Python，Java，CPP

JS Code：

functionfindBottomLeftValue(root){letmaxDepth=0;letres=root.val;dfs(root.left,0);dfs(root.right,0);returnres;functiondfs(cur,depth){if(!cur){return;}constcurDepth=depth+1;if(curDepth>maxDepth){maxDepth=curDepth;res=cur.val;}dfs(cur.left,curDepth);dfs(cur.right,curDepth);}}

Python Code:

classSolution(object): def__init__(self): self.res=0self.max_level=0deffindBottomLeftValue(self, root): self.res=root.valdefdfs(root, level): ifnotroot: returniflevel>self.max_level: self.res=root.valself.max_level=leveldfs(root.left, level+1) dfs(root.right, level+1) dfs(root, 0) returnself.res

Java Code:

classSolution { intmax = 0; Map<Integer,Integer> map = newHashMap<>(); publicintfindBottomLeftValue(TreeNoderoot) { if (root == null) return0; dfs(root,0); returnmap.get(max); } voiddfs (TreeNodenode,intlevel){ if (node == null){ return; } intcurLevel = level+1; dfs(node.left,curLevel); if (curLevel > max && !map.containsKey(curLevel)){ map.put(curLevel,node.val); max = curLevel; } dfs(node.right,curLevel); } }

CPP:

classSolution { public:int res; int max_depth = 0; voidfindBottomLeftValue_core(TreeNode* root, int depth) { if (root->left || root->right) { if (root->left) findBottomLeftValue_core(root->left, depth + 1); if (root->right) findBottomLeftValue_core(root->right, depth + 1); } else { if (depth > max_depth) { res = root->val; max_depth = depth; } } } intfindBottomLeftValue(TreeNode* root) { findBottomLeftValue_core(root, 1); return res; } }; 

复杂度分析

• 时间复杂度：$O(N)$，其中 N 为树的节点总数。
• 空间复杂度：$O(h)$，其中 h 为树的高度。