问题描述

设有如下二叉树：

x
    1
   /  \
  2    3
 / \  / \
4  5 6   7

其先序序列为：

xxxxxxxxxx
1 2 4 5 3 6 7

将该二叉树转成如下形式：

xxxxxxxxxx
 1
  \
   2
    \
     4
      \
       5
        \
         3
          \
           6
            \
             7

Python 实现

xxxxxxxxxx
# coding: utf8
​
​
class TreeNode(object):
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
​
​
class Solution(object):
    def reorder_binary_tree(self, root):
        # visited[0] 是前一次遍历到的节点
        visited = [None]
​
        def _reorder_binary_tree(node):
            if node is None:
                return
            left = node.left
            right = node.right
            node.left = node.right = None
            if visited[0] is None:
                visited[0] = node
            else:
                visited[0].right = node
                visited[0] = node
            _reorder_binary_tree(left)
            _reorder_binary_tree(right)
​
        _reorder_binary_tree(root)
​
​
def test():
    ########
    # 测试树为：
    #       1
    #     /  \
    #    2    3
    #   / \  / \
    #  4  5 6   7
    #
    # 其先序遍历序列为：
    # 1 2 4 5 3 6 7
    #
    # 预期输出为：
    # 1
    #  \
    #   2
    #    \
    #     4
    #      \
    #      ...
    ##########
​
    # 构造测试树
    nodes = [TreeNode(i) for i in range(1, 8)]
    nodes[0].left = nodes[1]
    nodes[0].right = nodes[2]
    nodes[1].left = nodes[3]
    nodes[1].right = nodes[4]
    nodes[2].left = nodes[5]
    nodes[2].right = nodes[6]
    root = nodes[0]
    del nodes
​
    # 转换
    Solution().reorder_binary_tree(root)
​
    # 验证
    temp = root
    nodes = []
    while temp is not None:
        # 左子树必须为空
        assert temp.left is None
        # 输出 temp.val
        print(temp.val)
        nodes.append(temp.val)
        # 去右子树
        temp = temp.right
    assert nodes == [1, 2, 4, 5, 3, 6, 7]
​
​
if __name__ == "__main__":
    test()