首页>itarticle>leetcode513. find bottom left tree value
leetcode513. find bottom left tree value
admin11月 13, 20200
找二叉树最下面一层,最左边的元素。
513. Find Bottom Left Tree Value
Given a binary tree, find the leftmost value in the last row of the tree.
Example 1:
1 2 3 4 5 6 7 8
Input:
2 / 1 3
Output: 1
Example 2:
1 2 3 4 5 6 7 8 9 10 11 12
Input:
1 / 2 3 / / 4 5 6 / 7
Output: 7
Note: You may assume the tree (i.e., the given root node) is not NULL.
算法1: 利用二叉树层次遍历算法,获得最下一层最左边元素。Leetcode 11ms
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
publicint(TreeNode root){ // if (root == null) return null; ArrayDeque<TreeNode> queue = new ArrayDeque<>(); queue.offer(root); TreeNode p = root; while (!queue.isEmpty()) { int size = queue.size(); for (int i = 0; i < size; i++) { p = queue.poll(); if (p.right != null) queue.offer(p.right); if (p.left != null) queue.offer(p.left); } } return p.val; }
算法2: 利用二叉树前序遍历算法,没进入新的一层获取第一个遍历的元素。Leetcode 6ms
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
//算法2:利用前序遍历找每次进入新层以后记录第一个元素 privateint newLevel; privateint ans; publicintfindBottomLeftValue01(TreeNode root){ preorderWalk(root, 0); return ans; } publicvoidpreorderWalk(TreeNode root, int level){ if (root == null) return; if (newLevel == level) { newLevel++; ans = root.val; } preorderWalk(root.left, level+1); preorderWalk(root.right, level+1); }
近期评论