iOS算法题（六）二叉树展开为链表

一 题目描述

给定一个二叉树，原地将它展开为链表。

例如，给定二叉树

    1
   / \
  2   5
 / \   \
3   4   6

将其展开为：

1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6

二 解题思路 - 前序遍历

2.1 思路1

不难看出，最终所求链表就是二叉树前序遍历的结果

1 -> 2 -> 3 -> 4 -> 5 -> 6

于是会想到一种错误的思路：前序遍历二叉树，每遍历一个节点，就设置

right = left, 然后left = null

作为一个开发者，有一个学习的氛围跟一个交流圈子特别重要，这是一个我的iOS交流群：413038000，不管你是大牛还是小白都欢迎入驻 ，分享BAT,阿里面试题、面试经验，讨论技术， 大家一起交流学习成长！

以下资料在群文件可自行下载！

image

上述思路会丢掉旧的 right
改进方案：在设置 right = left之前保存一下旧的 right，并将旧的 right 嫁接到最右下角

image image

2.2 思路1 - 前序遍历 - 递归实现

• 核心代码如下

/// 前序遍历- 递归遍历
- (void)flatten:(TreeNode *)root {
    if (root == nil) {
        return;
    }
    if (root.left != nil) {
        // 保留之前的right
        TreeNode *oldRight = root.right;
        // 将left嫁接到right
        root.right = root.left;
        // 清空left
        root.left = nil;
        // 将旧的right嫁接到root的最右下角
        TreeNode *rightMost = root;
        while (rightMost.right != nil) {
            rightMost = rightMost.right;
        }
        rightMost.right = oldRight;
    }
    [self flatten:root.right];  // 依次递归遍历右节点
}

时间复杂度O(n)，空间复杂度O(n)

• 运行结果如下

2019-11-30 17:35:57.465116+0800 09_Tree[18483:712676] 1
2019-11-30 17:35:57.465311+0800 09_Tree[18483:712676] 2
2019-11-30 17:35:57.465405+0800 09_Tree[18483:712676] 3
2019-11-30 17:35:57.465494+0800 09_Tree[18483:712676] 4
2019-11-30 17:35:57.465581+0800 09_Tree[18483:712676] 5
2019-11-30 17:35:57.465671+0800 09_Tree[18483:712676] 6

2.3 思路1 - 前序遍历 - 迭代实现

/// 前序遍历- 非递归遍历
- (void)flaten1:(TreeNode *)root {
    while (root != nil) {
        if (root.left != nil) {
            TreeNode *oldRight = root.right;    // 先保留右边的节点
            root.right = root.left; // 将左子树节点嫁接到右子树上
            root.left = nil;    // 将左子树清空

            // 找出右子树中最右边,最深的节点
            TreeNode *rightMost = root;
            while (rightMost.right != nil) {
                rightMost = rightMost.right;
            }
            rightMost.right = oldRight; // 将原来右节点嫁接到最右边最深的节点处
        }
        root = root.right;
    }
}

时间复杂度O(n)，空间复杂度O(1)

• 运行结果

2019-11-30 17:48:27.751169+0800 09_Tree[18689:720897] 1
2019-11-30 17:48:27.751369+0800 09_Tree[18689:720897] 2
2019-11-30 17:48:27.751502+0800 09_Tree[18689:720897] 3
2019-11-30 17:48:27.751606+0800 09_Tree[18689:720897] 4
2019-11-30 17:48:27.751697+0800 09_Tree[18689:720897] 5
2019-11-30 17:48:27.751787+0800 09_Tree[18689:720897] 6

三 解题思路 - 后序遍历

image

二叉树后序遍历（右 -> 左 -> root）的结果是

6 -> 5 -> 4 -> 3 -> 2 -> 1

，于是可以想到一种新思路。

后序二叉树，每遍历到一个节点，就让它的right指向上一个遍历到的节点，并清空它的left。

image image

• 核心代码如下

static TreeNode *prev;
/// 后序遍历 - 递归遍历
- (void)flatten2:(TreeNode *)root {
    if (root == nil) {
        return;
    }
    [self flatten2:root.right];
    [self flatten2:root.left];

    if (prev != nil) {
        root.right = prev;
        root.left = nil;
    }

    prev = root;
}

时间复杂度O(n)，空间复杂度O(n)

• 运行结果

2019-11-30 18:15:04.701001+0800 09_Tree[19192:737637] 1
2019-11-30 18:15:04.701164+0800 09_Tree[19192:737637] 2
2019-11-30 18:15:04.701292+0800 09_Tree[19192:737637] 3
2019-11-30 18:15:04.701396+0800 09_Tree[19192:737637] 4
2019-11-30 18:15:04.701493+0800 09_Tree[19192:737637] 5
2019-11-30 18:15:04.701580+0800 09_Tree[19192:737637] 6

---

---

项目链接地址- 06_ExpendTreeToLinked

作为一个开发者，有一个学习的氛围跟一个交流圈子特别重要，这是一个我的iOS交流群：413038000，不管你是大牛还是小白都欢迎入驻 ，分享BAT,阿里面试题、面试经验，讨论技术， 大家一起交流学习成长！

推荐阅读

iOS开发——最新 BAT面试题合集（持续更新中）

作者：路飞_Luck
链接：https://www.jianshu.com/p/7f4183e5e17a
来源：简书