扫码订阅《 》或入驻星球,即可阅读文章!

GOLANG ROADMAP

阅读模式

  • 沉浸
  • 自动
  • 日常
首页
Go友会
  • 城市
  • 校园
Go学院
  • Go小课
  • Go小考
  • Go实战
  • 精品课
Go求职
  • 求职辅导🔥
  • Offer收割社群
  • 企业题库
  • 面试宝典
Go宝典
  • 在线宝典
  • B站精选
  • 推荐图书
  • 每日博文
Go仓库
实验区
  • Go周边
  • Go下载
  • Go月刊
消息
更多
  • 用户中心

    • 我的信息
    • 推广返利
  • 玩转星球

    • 星球介绍
    • 角色体系
    • 星主权益
  • 支持与服务

    • 联系星主
    • 成长记录
    • 常见问题
    • 吐槽专区
  • 合作交流

    • 渠道合作
    • 课程入驻
    • 友情链接
author-avatar

GOLANG ROADMAP


首页
Go友会
  • 城市
  • 校园
Go学院
  • Go小课
  • Go小考
  • Go实战
  • 精品课
Go求职
  • 求职辅导🔥
  • Offer收割社群
  • 企业题库
  • 面试宝典
Go宝典
  • 在线宝典
  • B站精选
  • 推荐图书
  • 每日博文
Go仓库
实验区
  • Go周边
  • Go下载
  • Go月刊
消息
更多
  • 用户中心

    • 我的信息
    • 推广返利
  • 玩转星球

    • 星球介绍
    • 角色体系
    • 星主权益
  • 支持与服务

    • 联系星主
    • 成长记录
    • 常见问题
    • 吐槽专区
  • 合作交流

    • 渠道合作
    • 课程入驻
    • 友情链接

扫码订阅《 》或入驻星球,即可阅读文章!

一棵二叉树,求最大通路长度(即最大左右子树高度之和)


面试宝典 字节篇

题目:一棵二叉树,求最大通路长度(即最大左右子树高度之和)

参考答案:

该题与leetcode第104题同题型,定义TreeNode结构如下:

class TreeNode {

    int val;
    TreeNode left;
    TreeNode right;

    public TreeNode(int val) {
        this.val = val;
    }
}
1
2
3
4
5
6
7
8
9
10

解法一(递归求解)

class Solution {

    public int maxHeight(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return maxChildHeight(root.left) + maxChildHeight(root.right);
    }

    public int maxChildHeight(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftHeight = maxChildHeight(root.left);
        int rightHeight = maxChildHeight(root.right);
        return Math.max(leftHeight, rightHeight) + 1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

解法二(迭代求解)

public class Solution {

    public int maxHeight(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return maxChildHeight(root.left) + maxChildHeight(root.right);
    }

    public int maxChildHeight(TreeNode root) {
        int height = 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);

        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                height++;
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            }
        }
        return height;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30