二叉树中序搜索转双向链表——Bytedance的一条面试题

Posted on In

前言

之前出于无聊投了一次Bytedance的后端校招，刚刚收到一面，前面聊项目还是十分愉快的，到了算法部分，遇到了一个不是很常规的题目，很遗憾，当时并没有解出来，体现了我对于陌生题目的思考速度的欠缺，以及心态可能还是不够稳定，不过这也展现了宇宙条手撕代码的难度，居然会出LeetCode上没有的题(Leetcode114有一点相似，但并不完全一样)特此记录分享一下。

题目描述

题目其实挺有意思，二叉树和双向链表很相像(说实话在此之前从来没有注意过这一点)，都是有两个指针指向两个不同的地方，要求将二叉树的中序遍历转换为双向链表，原地转换，不允许借助辅助空间。

我在geekforgeek上居然找到了这一题的图，大概是这个样子的

思路

二叉树的题目，绝大多数情况下都是递归，不过怎么递归是关键，当时我纠结半天没有想出来的地方，在于我有点纠结递归返回什么，怎么返回，后来发现无所谓，直接返回自己就可以，写个makeList这种函数，将左右当做黑盒，直接返回本身节点，上一层节点要调用的时候，应该找左边的最后一个节点，以及右边的第一个节点，也就是说将寻找节点的任务交给上一层。

具体代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public static TreeNode makeList(TreeNode root){
    if(root == null)
        return null;
    
    TreeNode prev = makeList(root.left);
    //每次都默认左边右边都已经是一个构造好了的双向链表
    //左边就找最右的节点，建立与当前节点的联系
    if(prev != null){
        while(prev.right != null)
            prev = prev.right;
        prev.right = root;
    }
    root.left = prev;
    //右边则找第一个节点
    TreeNode next = makeList(root.right);
    if(next != null){
        while(next.left != null)
            next = next.left;
        next.left = root;
    }
    root.right = next;
    return root;
}

感想

虽然完了之后琢磨了下，很快解了出来，但是面试的时候没做出来，终归还是凉凉，面试的时候个人实力能发挥50%就算很好的了，深有体会，只能不断提高个人实力和做题的熟练度了，关键是思路与方法，例如这题是一个很明显的递归，弄清递归条件，把递归其实可以就当做一个黑盒使用，这类问题自然也迎刃而解了，现场没想出来这种不是很难的题目，归根结底，还是因为菜，菜有时不光是技术能力，也包括临场应变和心态，多多努力吧，唉~~