LeetCode-114-二叉树展开为链表

  |   0 评论   |   0 浏览

题目

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

 

例如,给定二叉树

    1
   / \
  2   5
 / \   \
3   4   6
将其展开为:

1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6

解法-递归

题目要求原地展开,故不能使用数组类变量存储全部节点值再重构树。将左右子树分别递归展开,将原左子树变为节点的右子树,再将原右子树变为当前右子树最右节点的右子树。

go代码实现

func flatten(root *TreeNode)  {

	if root == nil {
		return
	}

	flat(root)
}

func flat(node *TreeNode) {

	if node == nil {
		return
	}

	flat(node.Left)
	flat(node.Right)

	var temp *TreeNode = node.Right

	node.Right, node.Left = node.Left, nil

	for node.Right != nil {
		node = node.Right
	}
	node.Right = temp

}

image.png

或者简化一下代码:

func flatten(root *TreeNode)  {

	if root == nil {
		return
	}

	flat(root.Left)
	flat(root.Right)

	var temp *TreeNode = root.Right

	root.Right, root.Left = root.Left, nil

	for root.Right != nil {
		root = root.Right
	}
	root.Right = temp
}

标题:LeetCode-114-二叉树展开为链表
作者:guobingwei
地址:http://guobingwei.tech/articles/2020/10/25/1603563225349.html