114. Flatten Binary Tree to Linked List

把一棵二叉树变为链表

思路：先序遍历的非递归实现，prev记录先序遍历的上一个，cur是当前的，把prev的左子树指向None，右子树指向cur即可，然后prev=cur

Python:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def flatten(self, root):
        """
        :type root: TreeNode
        :rtype: void Do not return anything, modify root in-place instead.
        """
        # 6 star, 没理解，需多看
        
        if not root:
            return
        stack = [root]
        prev = TreeNode(None)
        while stack:
            cur = stack.pop()
            if cur.right:
                stack.append(cur.right)
            if cur.left:
                stack.append(cur.left)
            prev.left, prev.right = None, cur
            prev = cur

Go:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func flatten(root *TreeNode)  {
	if root == nil {return }
	var cur *TreeNode
	stack := []*TreeNode {root}
	prev := &TreeNode{0, nil, nil}
	for len(stack) > 0 {
		cur, stack = stack[len(stack)-1], stack[:len(stack)-1]
		if cur.Right != nil {
			stack = append(stack, cur.Right)
		}
		if cur.Left != nil {
			stack = append(stack, cur.Left)
		}
		prev.Left, prev.Right = nil, cur
		prev = cur

	}

}