513. Find Bottom Left Tree Value

眯眯眼的猫头鹰

发布于 2019-11-19 15:50:03

4140

发布于 2019-11-19 15:50:03

文章被收录于专栏：眯眯眼猫头鹰的小树杈眯眯眼猫头鹰的小树杈

题目要求

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:

Output: 7

Note: You may assume the tree (i.e., the given root node) is not NULL. 现有一棵二叉树，要求找到树中最后一行最左边的节点的值。

思路和代码

这题其实就是考察树的遍历。那么如何遍历树能够找到最后一行最左边的值呢？首先一个就是水平遍历，逐个遍历树的每一行，每次都记录该行最左边的值。当没有下一行时，则返回当前记录的行的最左边的值。

还有一种方法就是通过后序遍历。每次遍历时将当前节点所在的深度传递过去，并且和已知的最远行数进行比较。如果深度大于当前的行数，则说明该值是最远处的最左边的值。

代码如下：

    int depth = 0;
    int value = 0;
    public int findBottomLeftValue(TreeNode root) {
        findBottomLeftValue(root, 1);
        return value;
    }

    public void findBottomLeftValue(TreeNode root, int depth) {
        if (root == null) return;
        if (root.left == null && root.right == null && depth > this.depth) {
            value = root.val;
            this.depth = depth;
            return;
        }
        findBottomLeftValue(root.left, depth+1);
        findBottomLeftValue(root.right, depth+1);
    }

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度