LeetCode 114. 二叉树展开为链表

LeetCode 114. 二叉树展开为链表

题目描述

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

例如,给定二叉树


将其展开为:

题目地址

中文版

英文版

 

第一种实现方式

参考题目描述,组后实现的链表是
1-2-3-4-5-6
这其实就是 二叉树的前序 遍历得到的结果
所以我们用前序遍历访问一次二叉树,每访问一个元素,就将这个元素放到队列中
之后再遍历这个队列,将前面一个节点的.right 指针指向 后一个元素
这么迭代的遍历一边后,得到的结果就是一个往右的展开链表了

代码实现

class Solution(object):
	def flatten(self, root):
		"""
		:type root: TreeNode
		:rtype: None Do not return anything, modify root in-place instead.
		"""
		if(not root):
			return
		queue = []
		def recursion(root):
			if(not root):
				return
			queue.append(root)
			recursion(root.left)
			recursion(root.right)
		recursion(root)
		head = queue.pop(0)
		head.left = None
		head.right = None
		while queue:
			tmp = queue.pop(0)
			tmp.left = None
			tmp.right = None
			head.right = tmp
			head = tmp
                                                                                        

第二种实现方式

这种实现方式是采用后序遍历,先左节点再右节点,当遍历到根节点的时候,就将左右子树串起来
先是找到左节点的 “最右子节点” ,然后将根节点的右子树挂到这个“最右子节点”的右边
之后将左节点挂到根节点的右边,将根节点的左节点设置为null

代码实现

class Solution(object):
	def flatten(self, root):
		"""
		:type root: TreeNode
		:rtype: None Do not return anything, modify root in-place instead.
		"""
		if(not root):
			return None
                # 这里采用后序遍历的方式,遍历完左右子节点后,再将右节点挂到左节点的“最右边”
                # 之后再将根节点root.left->null,根节点root.right->左节点
                # 之后不断递归,最终就可以将整个树串联起来了
		def helper(root):
			if(not root):
				return 
			helper(root.left)
			helper(root.right)
                        # 如果左节点不为空则继续,右节点不为空/或者为空本身就满足条件不用判断
			if(root.left):
                                # 先将根的左边拿出赋给pre变量
				pre = root.left
                                # 接着一直遍历到pre的最右边节点
				while pre.right:
					pre = pre.right
                                # 然后把根节点的右节点 赋给 pre的右边
                                # 再将根节点的right->指向根节点的left,就把左右节点串起来
                                # 最后一步,不用忘记把根节点的left指向null
				pre.right = root.right
				root.right = root.left
				root.left = None
		helper(root)
                                                                                         

第三种实现方式

这种方式需要借助一个stack,先把根节点放入栈中
之后弹出根节点,再将跟节点的右节点,左节点分别放入栈中,注意是先右后左
这样下次再出栈的时候,弹出的就是左边节点的元素了,这种方式入栈出栈,其结果就是前序遍历,跟第一种方式很类似,但比第一种更高效
最后再将pre节点跟后面的节点串起来,整个树就变成链表了

代码实现

class Solution(object):
    def flatten(self, root):
        """
        :type root: TreeNode
        :rtype: None Do not return anything, modify root in-place instead.
        """
        if not root:
            return None
        # 先把根节点加入到stack中
        stack = [root]
        # 再增加一个pre节点,然后每次迭代到下个元素后,就将pre.right指向下个元素
        pre = TreeNode(-1)
        while stack:
            # 从stack中弹出最后加入的元素,然后将pre.left->null
            # pre.right->刚弹出的这个元素
            node = stack.pop()
            pre.left = None
            pre.right = node
            # 如果左右子节点都不为null,则分别加入stack中
            # 注意这里是先加入right,再left节点
            if(node.right!=None):
                stack.append(node.right)
            # 第一次遍历时候,先加入right再left,stack内容就是[5,2]
            # 第二次再遍历,弹出2,再加入左右节点,stack的内容变成了[5,4,3]
            if(node.left!=None):
                stack.append(node.left)
            pre = node	
                                                                              

第四种实现方式

这种实现方式的思路非常巧妙,它也是用递归,但跟前序的遍历顺序正好是相反的,也不是后序,应该叫倒序的方式遍历
比如题目描述中的那个树,用前序的方式遍历,结果是
1-2-3-4-5-6, 如果用倒序的方式遍历就是
6-5-4-3-2-1
倒序就是先右边,再左边,最后中间,所以顺序跟前序正好相反
借助一个pre节点,当每次遍历到一个节点的时候,就将当前节点的right指向pre节点
然后再将当前节点赋给pre,不断的递归之后,就可以将整个树串成链表了

代码实现

class Solution(object):
	def flatten(self, root):
		"""
		:type root: TreeNode
		:rtype: None Do not return anything, modify root in-place instead.
		"""
		if(not root):
			return
                # 设置一个pre节点,有点类似单链表的反转的pre节点,一开始指向null
                # 然后每迭代一次,当前节点就执行pre,这么一路迭代下去之后,就反转了链表
                # 这里也是类似,先拿到最后一个节点,然后最后一个节点的right->pre
                # 接着self.pre = root ,这里的root就是最后一个节点(6)
                # 然后递归返回,下次再执行root.right->self.pre 就是 5.right->6
		self.pre = None
                # 递归遍历,但这个跟前序遍历相反,也不是后序遍历,应该叫反序遍历
                # 比如前序遍历是 1-2-3-4-5-6,反序遍历就是 6-5-4-3-2-1
		def recursion(root):
			if(not root):
				return
			recursion(root.right)
			recursion(root.left)
			root.left = None
			root.right = self.pre
			self.pre = root
		recursion(root)
                                                                                              

 

13 次阅读

发表评论

电子邮件地址不会被公开。