LEETCODE 114. 二叉树展开为链表

LEETCODE 114. 二叉树展开为链表

题目描述

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

    1
   / \
  2   5
 / \   \
3   4   6

将其展开为:

1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6

题目地址:
https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list/

解法1

展开后的链表是1->2->3->4->5->6,这个顺序就是二叉树前序遍历的顺序,我们用前序遍历的方式遍历这棵树,将结果保存到一个数组中,再把这个数组中的每个元素前后串联起来就可以了。

时间复杂度:O(N)

空间复杂度:O(N)

java代码:

class Solution {
	public void flatten(TreeNode root) {
		if(root==null) {
			return;
		}
		LinkedList<TreeNode> res = new LinkedList<TreeNode>();
		//前序遍历整棵二叉树
		dfs(root,res);
		TreeNode head = res.removeFirst();
		head.left = null;
		//遍历链表,将链表中的TreeNode节点前后串联起来
		while(res.size()>0) {
			TreeNode tmp = res.removeFirst();			
			tmp.left = null;
			head.right = tmp;
			head = head.right;
		}	
	}
	
	//前序遍历整棵二叉树,并将遍历的结果放到数组中
	void dfs(TreeNode root, List<TreeNode> res) {
		if(root==null) {
			return;
		}
		res.add(root);
		dfs(root.left,res);
		dfs(root.right,res);
	}
}
                                                                           

python代码:

class Solution(object):
	def flatten(self, root):
		if not root:
			return
		queue = []
		# 前序遍历整棵二叉树,并将遍历的结果放到数组中
		def dfs(root):
			if not root:
				return
			queue.append(root)
			dfs(root.left)
			dfs(root.right)
		dfs(root)
		head = queue.pop(0)
		head.left = None
		# 遍历链表,将链表中的TreeNode节点前后串联起来
		while queue:
			tmp = queue.pop(0)
			tmp.left = None
			head.right = tmp
			head = tmp
                                                                 

解法2

解法1用队列作为辅助数据结构,完成二叉树的前序遍历。在解法2中则用作为辅助数据结构,同样也是来实现前序遍历。
下面这棵树,我们先将5放入栈中,再将2放入栈中,然后不断重复这个先右后左的顺序。

    1
   / \
  2   5
 / \   \
3   4   6

在遍历的过程中,同时也将前后的节点串联起来,当整个遍历结束后,二叉树就变成链表结构了。

时间复杂度:O(N)
空间复杂度:O(N)

java代码:

class Solution {
	public void flatten(TreeNode root) {
		if(root==null) {
			return;
		}
		Stack<TreeNode> stack = new Stack<TreeNode>();
		stack.add(root);
		TreeNode pre = new TreeNode(-1);
		while(stack.size()>0) {
			//用栈作为辅助数据结构,从栈中弹出元素后
			//先将右节点放到栈中,再将左节点放入栈中,模拟前序遍历
			TreeNode tmp = stack.pop();
			pre.left = null;
			pre.right = tmp;
			//先放入右节点,再放入左边点,顺序不能反了
			if(tmp.right!=null) {
				stack.add(tmp.right);
			}
			if(tmp.left!=null) {
				stack.add(tmp.left);
			}
			pre = pre.right;
		}
	}
}
                                                                                  

python代码:

class Solution(object):
	def flatten(self, root):
		if not root:
			return
		stack = [root]
		pre = TreeNode(-1)
		while stack:
			# 用栈作为辅助数据结构,从栈中弹出元素后
			# 先将右节点放到栈中,再将左节点放入栈中,模拟前序遍历
			tmp = stack.pop()
			pre.left,pre.right = None,tmp
			# 先放入右节点,再放入左边点,顺序不能反了
			if tmp.right:
				stack.append(tmp.right)
			if tmp.left:
				stack.append(tmp.left)
			pre = tmp
                                                                                

解法3

我们采用后序遍历的方式,也就是 左节点-右节点-打印根节点 这个顺序遍历二叉树。
当遍历到根节点后,我们对根节点的左右子树做一些调整。

    1
   / \
  2   3

右节点挂到左节点的最右边

    1
   /
  2
   \
    3

再将整个左子树挂到根节点的右边,这样就可以将整棵树变成链表结构了。

    1
     \
      2
       \
        3

时间复杂度:O(N)
空间复杂度:O(h),h是树高度

java代码:

class Solution {
	public void flatten(TreeNode root) {
		helper(root);
	}
	
	void helper(TreeNode root) {
		if(root==null) {
			return;
		}
		helper(root.left);
		helper(root.right);
		//将右子树挂到 左子树的最右边
		//再将整个左子树挂到根节点的右边
		if(root.left!=null) {
			TreeNode pre = root.left;
			while(pre.right!=null) {
				pre = pre.right;
			}
			pre.right = root.right;
			root.right = root.left;
			root.left = null;
		}
	}
}
                                                             

python代码:

class Solution(object):
	def flatten(self, root):
		def dfs(root):
			if not root:
				return
			dfs(root.left)
			dfs(root.right)
			# 将右子树挂到 左子树的最右边
			# 再将整个左子树挂到根节点的右边
			if root.left:
				pre = root.left
				while pre.right:
					pre = pre.right
				pre.right = root.right
				root.right = root.left
				root.left = None
		dfs(root)
                                                               

解法4

前序遍历是:打印根节点-左节点-右节点 这样的顺序,如果是:右节点-左节点-打印根节点  这样完全相反的顺序遍历呢?
这样遍历完之后,正好跟前序遍历是相反的。
前序遍历完是1,2,3,4,5,6,按照这种新的方式遍历其结果是:6,5,4,3,2,1
既然得到了反向的顺序,那么就可以把前后节点串联起来,当遍历到根节点1的时候,整个串联就完成了,二叉树就变成了链表。
null<-6<-5<-4<-3<-2<-1

时间复杂度:O(N)
空间复杂度:O(h),h是树高度

java代码:

class Solution {
	public void flatten(TreeNode root) {
		helper(root);
	}
	
	TreeNode pre = null;
	void helper(TreeNode root) {
		if(root==null) {
			return;
		}
		//右节点-左节点-根节点 这种顺序正好跟前序遍历相反
		//用pre节点作为媒介,将遍历到的节点前后串联起来
		helper(root.right);
		helper(root.left);
		root.left = null;
		root.right = pre;
		pre = root;
	}
}
                                                                     

python代码:

class Solution(object):
	def flatten(self, root):
		self.pre = None
		def dfs(root):
			if not root:
				return None
			# 右节点-左节点-根节点 这种顺序正好跟前序遍历相反
			# 用pre节点作为媒介,将遍历到的节点前后串联起来
			dfs(root.right)
			dfs(root.left)
			root.left = None
			root.right = self.pre
			self.pre = root
		dfs(root)
                                                                            

(全文完)

6 次阅读

发表评论

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