首页 > itarticle > leetcode解题-flatten binary tree to linked list

leetcode解题-flatten binary tree to linked list

admin 11月 11, 2020 0

描述

Given a binary tree, flatten it to a linked list in-place.

For example,
Given
    1
   / 
  2   5
 /    
3   4   6
The flattened tree should look like:
1

2

3

4

5

6
Hints:
If you notice carefully in the flattened tree, each node’s right child points to the next node of a pre-order traversal.

分析

这道题有点莫名其妙，不知道初衷是什么。按照提示，先序遍历，把每个被访问的节点右儿子设为下一个要访问的节点。迭代法用栈实现，时间O(n)，空间O(logn)。

代码

Python

class (object):
    def flatten(self, root):
        """
        :type root: TreeNode
        :rtype: void Do not return anything, modify root in-place instead.
        """
        
        ss = []
        if root:
            ss.append(root)
        while ss:
            cur = ss.pop()
            if cur.right:
                ss.append(cur.right)
            if cur.left:
                ss.append(cur.left)
            # visit cur
            cur.left = None
            if ss:
                cur.right = ss[-1]