114. 二叉树展开为链表

mid

给你二叉树的根结点 root ，请你将它展开为一个单链表：

• 展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
• 展开后的单链表应该与二叉树 先序遍历 顺序相同

栈 + 先序遍历

用 preNode 记录上一个节点

func flatten(root *TreeNode) {
	if root == nil {
		return
	}
	stack := make([]*TreeNode, 0)
	stack = append(stack, root)
	var preNode *TreeNode
	for len(stack) != 0 {
		curNode := stack[len(stack)-1]
		stack = stack[:len(stack)-1]

		if preNode != nil {
			preNode.Left = nil
			preNode.Right = curNode
		}

		if curNode.Right != nil {
			stack = append(stack, curNode.Right)
		}
		if curNode.Left != nil {
			stack = append(stack, curNode.Left)
		}
		preNode = curNode
	}
}

寻找前驱节点

使空间复杂度降为 $O(1)$

    1
   / \
  2   5
 / \   \
3   4   6

# 将 1 的左子树插入到右子树的地方
    1
     \
      2         5
     / \         \
    3   4         6       
    
# 将原来的右子树接到左子树的最右边节点
    1
     \
      2          
     / \          
    3   4  
         \
          5
           \
            6
            
 # 将 2 的左子树插入到右子树的地方
    1
     \
      2          
       \          
        3       4  
                 \
                  5
                   \
                    6   
        
 # 将原来的右子树接到左子树的最右边节点
    1
     \
      2          
       \          
        3      
         \
          4  
           \
            5
             \
              6         
  

func flatten(root *TreeNode) {
	if root == nil {
		return
	}

	for root != nil {
		if root.Left == nil {
			root = root.Right
		} else {
			// 找到左子树的最右节点pre
			pre := root.Left
			for pre.Right != nil {
				pre = pre.Right
			}
			// 将右子树接到pre右
			pre.Right = root.Right
			// 将左子树变成右子树
			root.Right = root.Left
			root.Left = nil
			// 考虑下一个节点
			root = root.Right
		}
	}
}