leetcode 114 二叉树展开为链表
z
 2019-07-02 16:34:55  

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

例如，给定二叉树

        1
   / \
  2   5
 / \   \
3   4   6

将其展开为：

1
2
3
4
5
6
7
8
9
10
11
1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6

  1. 每一次把根节点的右子树拼接在左子树的右子树上

    例如：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    		1  <- cur                  1
       / \												  \
      2   5														2  <- cur
     / \   \			    ===>			  	/	  \							===> ...
    3   4   6											 3		  4
    			 / \															\
    			7   8																6
    																				 /	\
    																				7			8
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    class Solution(object):
        def flatten(self, root):
            """
            :type root: TreeNode
            :rtype: None Do not return anything, modify root in-place instead.
            """
            cur = root
            while cur:
                if cur.left:
                    p = cur.left
                    while p.right: p = p.right
                    p.right = cur.right
                    cur.right = cur.left
                    cur.left = None
                cur = cur.right

  2. 依次像左遍历，并把当前节点的右子树放到列表中，当遍历到最左的叶子节点时，pop列表中最近的一个右子树，继续

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    class Solution(object):
        def flatten(self, root):
            """
            :type root: TreeNode
            :rtype: None Do not return anything, modify root in-place instead.
            """
            pre = None
            rights = []
            rights.append(root)
            while rights:
                p = rights.pop()
                while p:
                    if p.right:
                        rights.append(p.right)
                    if not pre:
                        pre = p
                    else:
                        pre.right = p
                        pre = pre.right
                    p = p.left
                    pre.left = None