《每周一道算法题》（六）二叉树展开为链表

一 题目描述

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

例如，给定二叉树

    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

image.png

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

image.png image.png

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.png

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

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

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

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

image.png image.png

• 核心代码如下

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

---

本文参考MJ老师的每周一道算法题

---

项目链接地址- 06_ExpendTreeToLinked

---

每周一道算法题 - 笔记

---