LeetCode--513.找树左下角的值（二叉树）

题目描述

给定一个二叉树的根节点root，请找出该二叉树的最底层 最左边节点的值。

假设二叉树中至少有一个节点。

示例 1:

输入: root = [2,1,3] 输出: 1

示例 2:

输入: [1,2,3,4,null,5,6,null,null,7] 输出: 7

提示:

• 二叉树的节点个数的范围是[1,10^4]
• -231 <= Node.val <= 231 - 1

代码

迭代法

/** * 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; * } * } */classSolution{// 迭代法 层序遍历publicintfindBottomLeftValue(TreeNoderoot){intresult=root.val;if(root.left==null&&root.right==null)returnresult;// 分层存放Queue<TreeNode>que=newArrayDeque<>();que.add(root);while(!que.isEmpty()){intsize=que.size();result=que.peek().val;for(inti=0;i<size;i++){TreeNodenode=que.poll();if(node.left!=null)que.add(node.left);if(node.right!=null)que.add(node.right);}}returnresult;}}

递归法

/** * 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; * } * } */classSolution{publicintresult;publicintmaxDepth=0;publicvoidtraverse(TreeNodenode,intdepth){if(node==null)return;// 前序遍历 先处理中间节点if(depth>maxDepth&&node.left==null&&node.right==null){maxDepth=depth;result=node.val;return;}// 处理左节点if(node.left!=null){depth++;traverse(node.left,depth);depth--;//回溯}// 处理右节点if(node.right!=null){depth++;traverse(node.right,depth);depth--;//回溯}return;}publicintfindBottomLeftValue(TreeNoderoot){traverse(root,1);returnresult;}}