leetcode513. Find Bottom Left Tree Value

513. Find Bottom Left Tree Value

Given a binary tree, find the leftmost value in the last row of the tree.

Example 1: Input: 2 / \ 1 3 Output: 1 Example 2: Input: 1 / \ 2 3 / / \ 4 5 6 / 7 Output: 7

解法

层次遍历，每层从最右边开始遍历，最后一个结点即为最左边的结点，取该结点的值输出。

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public int findBottomLeftValue(TreeNode root) { int ret = -1; if (root == null) { return ret; } Queue<TreeNode> queue = new LinkedList<TreeNode>(); queue.offer(root); TreeNode temp = null; while (!queue.isEmpty()) { temp = queue.poll(); if (temp.right != null) { queue.offer(temp.right); } if (temp.left != null) { queue.offer(temp.left); } } return temp.val; } }

解法二

记录每层的第一个结点，最后输出该结点。

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public int findBottomLeftValue(TreeNode root) { int ret = -1; if (root == null) { return ret; } Queue<TreeNode> queue = new LinkedList<TreeNode>(); queue.offer(root); while (!queue.isEmpty()) { int size = queue.size(); ret = queue.peek().val; for (int i = 0; i < size; i++) { TreeNode temp = queue.poll(); if (temp.left != null) { queue.offer(temp.left); } if (temp.right != null) { queue.offer(temp.right); } } } return ret; } }

解法三

DFS：记录每一层的第一个结点。

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public int findBottomLeftValue(TreeNode root) { int[] result = new int[]{0, root.val}; find(root, 0, result); return result[1]; } private void find(TreeNode root, int level, int[] result) { if (root == null) { return; } if (level > result[0]) { result[0] = level; result[1] = root.val; } find(root.left, level + 1, result); find(root.right, level + 1, result); } }