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

做题记录

• 今日二刷

• 找出最左结点的值

• 注意：最左：最底层 + 最左

• 迭代法

  层序遍历

  队列最后出去的那一个元素就是要找的元素

  注意：往队列里面放元素的时候需要先放 右节点 然后才是放 左节点

• 递归法

  求出树的高度

  判断是从左树还是右树找目标

  递归条件：

        if(root.left==null&&root.right==null){
          return root.val;
        }
  

代码实现

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int findBottomLeftValue(TreeNode root) {
      Deque<TreeNode> queue=new ArrayDeque<>();
      queue.offer(root);
      int res=0;
      while(!queue.isEmpty()){
        TreeNode top=queue.poll();
        res=top.val;
        if(top.right!=null)queue.offer(top.right);
        if(top.left!=null)queue.offer(top.left);
      }
      return res;

    }
}


//递归
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int findBottomLeftValue(TreeNode root) {
      if(root.left==null&&root.right==null){
        return root.val;
      }
      int leftH=height(root.left);
      int rightH=height(root.right);
      if(leftH>=rightH){
        return findBottomLeftValue(root.left);
      }else{
        return findBottomLeftValue(root.right);
      }
    }
    public int height(TreeNode root){
      if(root==null){
        return 0;
      }
      int left=height(root.left);
      int right=height(root.right);
      return Math.max(left,right)+1;
    }
    
}

题目链接

513. 找树左下角的值