给定一个二叉树的 根节点 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
大体思路就是从上到下遍历整棵树,遍历的时候记录下一层的第一个值(就是最左边的值)
package leetCode;
import entity.TreeNode;
import java.util.HashMap;
import java.util.Map;
/**
* 513. 找树左下角的值
* 给定一个二叉树的 根节点 root,请找出该二叉树的 最底层 最左边 节点的值。
* <p>
* 假设二叉树中至少有一个节点。
* <p>
* 示例 1:
* 输入: root = [2,1,3]
* 输出: 1
* <p>
* 示例 2:
* 输入: [1,2,3,4,null,5,6,null,null,7]
* 输出: 7
*
* @author
* @date 2022-06-22 09:25:26
*/
public class LeetCode513 {
public static void main(String[] args) {
TreeNode root = new TreeNode(1, new TreeNode(2, new TreeNode(4), null), new TreeNode(3, new TreeNode(5), new TreeNode(6, new TreeNode(7), null)));
System.out.println(findBottomLeftValue(root));
}
/**
* 找树左下角的值
*
* @param root
* @return
*/
public static int findBottomLeftValue(TreeNode root) {
TreeNode curr = root;
Map<String, Integer> map = new HashMap<>(16);
map.put("layer", 0);
map.put("tar", null);
getList(1, map, curr);
return map.get("tar");
}
/**
* 递归遍历每个节点,当当前层数大于记录的层数时,就记录第一个节点,最后得到的就是最底层的最左变的节点值
*
* @param currLayer 当前层数
* @param map 记录之前的层数和目标值
* @param curr
*/
private static void getList(int currLayer, Map<String, Integer> map, TreeNode curr) {
if (curr == null) {
return;
}
if (currLayer > map.get("layer")) {
System.out.println(curr.val);
map.put("tar", curr.val);
map.put("layer", currLayer);
}
getList(currLayer + 1, map, curr.left);
getList(currLayer + 1, map, curr.right);
}
}
package entity;
/**
*
* @author
* @date 2022-06-22 09:37:36
*/
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
TreeNode() {
}
public TreeNode(int val) {
this.val = val;
}
public TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}