返回其层次遍历结果：

[ [3], [9,20], [15,7] ] 

题解

我们数据结构的书上教的层序遍历,就是利用一个队列,不断的把左子树和右子树入队。但是这个题目还要要求按照层输出。所以关键的问题是： 如何确定是在同一层的。 我们很自然的想到： 如果在入队之前,把上一层所有的节点出队,那么出队的这些节点就是上一层的列表。 由于队列是先进先出的数据结构,所以这个列表是从左到右的。

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> res = new LinkedList<>(); if (root == null) { return res; } LinkedList<TreeNode> queue = new LinkedList<>(); queue.add(root); while (!queue.isEmpty()) { int size = queue.size(); List<Integer> currentRes = new LinkedList<>(); // 当前队列的大小就是上一层的节点个数, 依次出队 while (size > 0) { TreeNode current = queue.poll(); if (current == null) { continue; } currentRes.add(current.val); // 左子树和右子树入队. if (current.left != null) { queue.add(current.left); } if (current.right != null) { queue.add(current.right); } size--; } res.add(currentRes); } return res; } } 

这道题可不可以用非递归来解呢?

递归的子问题：遍历当前节点, 对于当前层, 遍历左子树的下一层层,遍历右子树的下一层

递归结束条件: 当前层,当前子树节点是 null

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> res = new LinkedList<>(); if (root == null) { return res; } levelOrderHelper(res, root, 0); return res; } /** * @param depth 二叉树的深度 */ private void levelOrderHelper(List<List<Integer>> res, TreeNode root, int depth) { if (root == null) { return; } if (res.size() <= depth) { // 当前层的第一个节点,需要 new 一个 list 来存当前层. res.add(new LinkedList<>()); } // depth 层,把当前节点加入 res.get(depth).add(root.val); // 递归的遍历下一层. levelOrderHelper(res, root.left, depth + 1); levelOrderHelper(res, root.right, depth + 1); } } 

二叉树转链表(快手)

这是 Leetcode 104 题。 给定一个二叉树，原地将它展开为链表。

例如，给定二叉树

 1 / \ 2 5 / \ \ 3 4 6 

将其展开为：

1 \ 2 \ 3 \ 4 \ 5 \ 6 

这道题目的关键是转换的时候递归的时候记住是先转换右子树，再转换左子树。 所以需要记录一下右子树转换完之后链表的头结点在哪里。注意没有新定义一个 next 指针，而是直接将 right 当做 next 指针,那么 Left 指针我们赋值成 null 就可以了。

class Solution { private TreeNode prev = null; public void flatten(TreeNode root) { if (root == null) return; flatten(root.right); // 先转换右子树 flatten(root.left); root.right = prev; // 右子树指向链表的头 root.left = null; // 把左子树置空 prev = root; // 当前结点为链表头 } } 

用递归解法,用一个 stack 记录节点,右子树先入栈，左子树后入栈。

class Solution { public void flatten(TreeNode root) { if (root == null) return; Stack<TreeNode> stack = new Stack<TreeNode>(); stack.push(root); while (!stack.isEmpty()) { TreeNode current = stack.pop(); if (current.right != null) stack.push(current.right); if (current.left != null) stack.push(current.left); if (!stack.isEmpty()) current.right = stack.peek(); current.left = null; } } } 

二叉树寻找最近公共父节点(快手)

Leetcode 236 二叉树的最近公共父亲节点

题解

从根节点开始遍历，如果 node1 和 node2 中的任一个和 root 匹配，那么 root 就是最低公共祖先。 如果都不匹配，则分别递归左、右子树，如果有一个 节点出现在左子树，并且另一个节点出现在右子树，则 root 就是最低公共祖先. 如果两个节点都出现在左子树，则说明最低公共祖先在左子树中，否则在右子树。

public class Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { //发现目标节点则通过返回值标记该子树发现了某个目标结点 if(root == null || root == p || root == q) return root; //查看左子树中是否有目标结点，没有为 null TreeNode left = lowestCommonAncestor(root.left, p, q); //查看右子树是否有目标节点，没有为 null TreeNode right = lowestCommonAncestor(root.right, p, q); //都不为空，说明做右子树都有目标结点，则公共祖先就是本身 if(left!=null&&right!=null) return root; //如果发现了目标节点，则继续向上标记为该目标节点 return left == null ? right : left; } } 

数据流求中位数(蚂蚁)

面了蚂蚁中台的团队,二面面试官根据汇报层级推测应该是 P9 级别及以上，在美国面我，面试风格偏硅谷那边。题目是 hard 难度的,leetcode 295 题。 这道题目是 Leetcode 的 hard 难度的原题。给定一个数据流，求数据流的中位数，求中位数或者 topK 的问题我们通常都会想用堆来解决。 但是面试官又进一步加大了难度，他要求内存使用很小，没有磁盘，但是压榨空间的同时可以忍受一定时间的损耗。且面试官不仅要求说出思路，要写出完整可经过大数据检测的 production code。

先不考虑内存

不考虑内存的方式就是 Leetcode 论坛上的题解。 基本思想是建立两个堆。左边是大根堆，右边是小根堆。 如果是奇数的时候，大根堆的堆顶是中位数。

例如：[1,2,3,4,5] 大根堆建立如下：

 3 / \ 1 2 

小根堆建立如下:

 4 / 5 

偶数的时候则是最大堆和最小堆顶的平均数。

例如: [1, 2, 3, 4]

大根堆建立如下：

 2 / 1 

小根堆建立如下:

 3 / 4 

然后再维护一个奇数偶数的状态即可求中位数。

public class MedianStream { private PriorityQueue<Integer> leftHeap = new PriorityQueue<>(5, Collections.reverseOrder()); private PriorityQueue<Integer> rightHeap = new PriorityQueue<>(5); private boolean even = true; public double getMedian() { if (even) { return (leftHeap.peek() + rightHeap.peek()) / 2.0; } else { return leftHeap.peek(); } } public void addNum(int num) { if (even) { rightHeap.offer(num); int rightMin = rightHeap.poll(); leftHeap.offer(rightMin); } else { leftHeap.offer(num); int leftMax = leftHeap.poll(); rightHeap.offer(leftMax); } System.out.println(leftHeap); System.out.println(rightHeap); // 奇偶变换. even = !even; } } 

压榨内存

但是这样做的问题就是可能内存会爆掉。如果你的流无限大，那么意味着这些数据都要存在内存中，堆必须要能够建无限大。如果内存必须很小的方式，用时间换空间。

• 流是可以重复去读的, 用时间换空间;
• 可以用分治的思想,先读一遍流,把流中的数据个数分桶;
• 分桶之后遍历桶就可以得到中位数落在哪个桶里面,这样就把问题的范围缩小了。

public class Median { private static int BUCKET_SIZE = 1000; private int left = 0; private int right = Integer.MAX_VALUE; // 流这里用 int[] 代替 public double findMedian(int[] nums) { // 第一遍读取 stream 将问题复杂度转化为内存可接受的量级. int[] bucket = new int[BUCKET_SIZE]; int step = (right - left) / BUCKET_SIZE; boolean even = true; int sumCount = 0; for (int i = 0; i < nums.length; i++) { int index = nums[i] / step; bucket[index] = bucket[index] + 1; sumCount++; even = !even; } // 如果是偶数,那么就需要计算第 topK 个数 // 如果是奇数, 那么需要计算第 topK 和 topK+1 的个数. int topK = even ? sumCount / 2 : sumCount / 2 + 1; int index = 0; int indexBucketCount = 0; for (index = 0; index < bucket.length; index++) { indexBucketCount = bucket[index]; if (indexBucketCount >= topK) { // 当前 bucket 就是中位数的 bucket. break; } topK -= indexBucketCount; } // 划分到这里其实转化为一个 topK 的问题, 再读一遍流. if (even && indexBucketCount == topK) { left = index * step; right = (index + 2) * step; return helperEven(nums, topK); // 偶数的时候, 恰好划分到在左右两个子段中. // 左右两段中 [topIndex-K + (topIndex-K + 1)] / 2. } else if (even) { left = index * step; right = (index + 1) * step; return helperEven(nums, topK); // 左边 [topIndex-K + (topIndex-K + 1)] / 2 } else { left = index * step; right = (index + 1) * step; return helperOdd(nums, topK); // 奇数, 左边 topIndex-K } } } 

这里边界条件我们处理好之后,关键还是 helperOdd 和 helperEven 这两个函数怎么去求 topK 的问题. 我们还是转化为一个 topK 的问题,那么求 top-K 和 top(K+1)的问题到这里我们是不是可以用堆来解决了呢? 答案是不能,考虑极端情况。 中位数的重复次数非常多

eg: [100,100,100,100,100...] (1000 亿个 100) 

你的划分恰好落到这个桶里面,内存同样会爆掉。

再用时间换空间

假如我们的划分 bucket 大小是 10000,那么最大的时候区间就是 20000。(对应上面的偶数且落到两个分桶的情况) 那么既然划分到某一个 bucket 了,我们直接用数数字的方式来求 topK 就可以了,用堆的方式也可以,更高效一点,其实这里问题规模已经划分到很小了,两种方法都可以。 我们选用 TreeMap 这种数据结构计数。然后分奇数偶数去求解。

 private double helperEven(int[] nums, int topK) { TreeMap<Integer, Integer> map = new TreeMap<>(); for (int i = 0; i < nums.length; i++) { if (nums[i] >= left && nums[i] <= right) { if (!map.containsKey(nums[i])) { map.put(nums[i], 1); } else { map.put(nums[i], map.get(nums[i]) + 1); } } } int count = 0; int kNum = Integer.MIN_VALUE; int kNextNum = 0; for (Map.Entry<Integer, Integer> entry : map.entrySet()) { int currentCountIndex = entry.getValue(); if (kNum != Integer.MIN_VALUE) { kNextNum = entry.getKey(); break; } if (count + currentCountIndex == topK) { kNum = entry.getKey(); } else if (count + currentCountIndex > topK) { kNum = entry.getKey(); kNextNum = entry.getKey(); break; } else { count += currentCountIndex; } } return (kNum + kNextNum) / 2.0; } private double helperOdd(int[] nums, int topK) { TreeMap<Integer, Integer> map = new TreeMap<>(); for (int i = 0; i < nums.length; i++) { if (nums[i] >= left && nums[i] <= right) { if (!map.containsKey(nums[i])) { map.put(nums[i], 1); } else { map.put(nums[i], map.get(nums[i]) + 1); } } } int count = 0; int kNum = Integer.MIN_VALUE; for (Map.Entry<Integer, Integer> entry : map.entrySet()) { int currentCountIndex = entry.getValue(); if (currentCountIndex + count >= topK) { kNum = entry.getKey(); break; } else { count += currentCountIndex; } } return kNum; } 

至此,我觉得算是一个比较好的解决方案，leetcode 社区没有相关的解答和探索，欢迎大家交流。

总结

今年大环境真的不好，能不跳槽可以尽量呆着，我个人是觉得手上的事情没啥挑战，而且工资低，业务发展也不好就跳槽了。祝福大家拿到满意 offer。