[Leetcode]28.二叉树展开为链表

2021年11月20日 阅读数:3
这篇文章主要向大家介绍[Leetcode]28.二叉树展开为链表,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

题目:给你二叉树的根结点 root ,请你将它展开为一个单链表:
    展开后的单链表应该一样使用 TreeNode ,其中 right 子指针指向链表中下一个结点,而左子指针始终为 null 。
    展开后的单链表应该与二叉树 先序遍历 顺序相同。
node

示例 1:

输入:root = [1,2,5,3,4,null,6]
输出:[1,null,2,null,3,null,4,null,5,null,6]

示例 2:

输入:root = []
输出:[]

示例 3:

输入:root = [0]
输出:[0]

bash

思想一: 寻找前驱结点,咱们发如今前序遍历的时候,在遍历右子树前最后一个遍历的是左子树的最右结点,咱们只须要把右子树放到左子树的最右结点的右边,再进行当前结点的左右子树交换,便可实现二叉树的展开。3d

每次判断结点是否有左节点,若是没有,则已是排序好的了,再判断他的右节点便可。若是有,那么找他的左孩子的子树的最右结点,找到后把这个结点的右子树指向当前结点的右子树,而后把当前结点的右子树指向左子树,左子树指空。结束条件是向右遍历结束指针

func flatten(root *TreeNode) {
	cur :=root
	for cur !=nil{
		if cur.Left!=nil{
			next:=cur.Left
			pre := next
			for pre.Right!=nil{
				pre = pre.Right
			}
			pre.Right = cur.Right
			cur.Right = cur.Left
			cur.Left = nil
		}
		cur = cur.Right
	}
}

 思想二:经过上一层的next来解决下层的链接问题。每层的起始结点设置为最左的那个结点。实际上在添加Next结点的时候,会出现两种状况,第一种是父节点的左孩子指向右孩子,这种直接node.Left.Next = node.Right便可,第二种是父节点的右孩子指向父节点的右兄弟的左孩子,这种就须要经过父节点的Next结点的Left来定位,node.Right.Next = node.next.Left,断定条件是父节点是否有Next指向。code

func connect(root *Node) *Node {
	if root == nil{
		return root
	}
	for leftmost:=root;leftmost!=nil;leftmost = leftmost.Left{
		for node:=leftmost;node!=nil;node= node.Next{
			node.Left.Next = node.Right
			if node.Next!=nil{
				node.Right.Next = node.next.Left
			}
		}
	}
	return root
}

 

题目来源:https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-listblog