题目
给定一个二叉树的 根节点 root
,请找出该二叉树的 最底层 最左边 节点的值。
假设二叉树中至少有一个节点。
示例 1:
输入: root = [2,1,3]
输出: 1
示例 2:
输入: [1,2,3,4,null,5,6,null,null,7]
输出: 7
提示:
- 二叉树的节点个数的范围是
[1,10^4]
-2^31 <= Node.val <= 2^31 - 1
解题
方法一:DFS
思路
深度优先搜索找出二叉树中每一层最左边的节点,然后取出最下面那一层的最左节点的值返回。
应为节点的范围是 ,故二叉树最差情况下退化成链表也只有 1000 层,创建一个大于该值的数组(nodes
)用来存放每一层中最左边的节点。
传入根节点与其层数0开始深搜,节点为空是递归结束条件,对于每个节点直接把该节点存入数组中第 depth
个中,然后递归地搜索右子节点和左子节点(因为需要取的是最左节点,所以先搜右节点再搜左节点,这样的话如果能保证最后在数组中该层存储的一定是最左的节点)。
代码
class Solution {
private TreeNode[] nodes = new TreeNode[1010];
public int findBottomLeftValue(TreeNode root) {
dfs(root, 0);
for (int i = nodes.length - 1; i >= 0; i--) {
if (nodes[i] != null) return nodes[i].val;
}
return 0;
}
private void dfs(TreeNode node, int depth) {
if (node == null) return;
nodes[depth] = node;
dfs(node.right, depth + 1);
dfs(node.left, depth + 1);
}
}
优化
维护一个最大层数(max
)以及该层最左节点的值(ans
),在每次递归中,只有当前节点所在高度严格大于 max
时更新 max
以及把 ans
置为该节点的值,此时就应该先搜索左节点再搜右节点,因为这次每层只会更新一次,一定要保证某层第一次拿到的节点一定是该层的最左节点。
class Solution {
private int max, ans;
public int findBottomLeftValue(TreeNode root) {
dfs(root, 1);
return ans;
}
private void dfs(TreeNode node, int depth) {
if (node == null) return;
if (depth > max) {
ans = node.val;
max = depth;
}
dfs(node.left, depth + 1);
dfs(node.right, depth + 1);
}
}
评论区