首页 > itarticle > leetcode513. find bottom left tree value

leetcode513. find bottom left tree value

admin 11月 13, 2020 0

找二叉树最下面一层，最左边的元素。

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
 

public int (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：利用前序遍历找每次进入新层以后记录第一个元素
private int newLevel;
private int ans;
public int findBottomLeftValue01(TreeNode root) {
    preorderWalk(root, 0);
    return ans;
}
public void preorderWalk(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);
}
微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能