专栏 | 九章算法
网址 | http://www.jiuzhang.com
题目描述
给一棵二叉树，求出该二叉树最底层最左边的节点。
样例:
算法分析
这题有2个做法，一是宽度优先搜索，用每层的第一个节点来更新答案。二是深度优先搜索，当遇到一个节点的深度大于目前维护的最大深度时用这个节点来更新答案。
-
使用宽度优先搜索bfs，用每层的第一个节点更新Ans。时间复杂度O(n)。
-
使用深度优先搜索dfs，当我们第一次访问一个深度为depth的节点x（之前只访问过深度小于depth的节点）时，x一定是depth深度的最左节点，用这个节点更新Ans。即我们维护一个最大深度，当遍历到一个点的深度大于最大深度时，用这个节点来更新答案，并更新最大深度即可。时间复杂度O(n)。
参考程序
面试官角度分析
这道题是一道简单难度题，考点是基础数据结构二叉树和在二叉树中的搜索，用bfs和dfs均可。给出正确算法即可达到hire。lintcode相关问题