今日头条后端面试记录

正文

请到「今天看啥」查看全文

回来之后也对面试过程做了一些总结,就不夹带私货了,这篇文章主要对面试过程中的技术问题做一个复盘.

1. 求二叉树的最远节点的距离

这是一道 LeetCode 原题, 原题链接

求二叉树的最远距离节点间的节点. 首先总结几个规律:

1. 一棵树的直径要么完全在其左子树中,要么完全在其右子树中, 要么路过根节点.
2. 一棵树的直径 = 以该树中每一个节点为根节点, 求 路过根节点的最大直径, 所有节点的最大值就是这棵树的直径.
3. 求经过根节点的直径, 可以分解为: 求左子树的最深叶子 + 右子树的最深叶子.

所以我们要做:

1. 递归的求 每一个节点的 路过根节点的直径(求当前节点的左子树最深叶子和右子树的最深叶子) ,取其最大值.
2. 求某一个节点的最深叶子, 就等于 他的 左子树最深叶子 + 1 和 右子树最深叶子 + 1 的较大值.
3. 在求最深叶子的时候, 其实是求出了当前节点直径的(左边最深叶子 + 右边最深叶子 + 2), 为了避免重复计算, 我们在递归求最深叶子的时候, 把直径也记录下来.)

代码如下:

   public int diameterOfBinaryTree(TreeNode root) {
       AtomicReference<Integer> ret = new AtomicReference<>(0);
        find(root, ret);
       return ret.get();
   }

   private int find(TreeNode node, AtomicReference<Integer> result) {
       if (node == null) return 0;
       int left = 0, right = 0;
       if (node.left != null) left = find(node.left,result) + 1;
       if (node.right != null) right = find(node.right,result) + 1;
       int tmp = Math.max(result.get(), left + right);
       result.set(tmp);
       return Math.max(left, right);
   }
复制代码

代码很简单, 就是递归的求节点的左子树最远叶子和右子树最远叶子. 然后在 计算过程中, 将 当前节点的直径 作为一个备选项存储,最后求最大直径即可.

2. Java的装箱与拆箱

Java在1.5添加了自动装箱和拆箱机制. 总的来说基本就是基本类型和对应的包装类型之间的自动转换.

请到「今天看啥」查看全文