LEETCODE 116. 填充每个节点的下一个右侧节点指针

LEETCODE 116. 填充每个节点的下一个右侧节点指针

Comments 0 Comment

题目描述

给定一个完美二叉树，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。初始状态下，所有 next 指针都被设置为 NULL。示例：输入：

{"$id":"1","left":{"$id":"2","left":{"$id":"3","left":null,"next":null,"right":null,"val":4},"next":null,"right":{"$id":"4","left":null,"next":null,"right":null,"val":5},"val":2},"next":null,"right":{"$id":"5","left":{"$id":"6","left":null,"next":null,"right":null,"val":6},"next":null,"right":{"$id":"7","left":null,"next":null,"right":null,"val":7},"val":3},"val":1}

输出：

{"$id":"1","left":{"$id":"2","left":{"$id":"3","left":null,"next":{"$id":"4","left":null,"next":{"$id":"5","left":null,"next":{"$id":"6","left":null,"next":null,"right":null,"val":7},"right":null,"val":6},"right":null,"val":5},"right":null,"val":4},"next":{"$id":"7","left":{"$ref":"5"},"next":null,"right":{"$ref":"6"},"val":3},"right":{"$ref":"4"},"val":2},"next":null,"right":{"$ref":"7"},"val":1}

解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。

提示：
你只能使用常量级额外空间。
使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。

题目地址:
https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node/

迭代解法1

回想一下二叉树的层次遍历，用广度优先实现的时候，就是层层遍历，每层临时遍历的节点都会放到一个队列中。
队列中保存了第i层节点的信息，我们利用这个特点，将队列中的元素都串联一遍就可以了。

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

java代码:

class Solution {
	public Node connect(Node root) {
		if(root==null) {
			return root;
		}
		LinkedList<Node> queue = new LinkedList<Node>();
		queue.add(root);
		while(queue.size()>0) {
			int size = queue.size();
			//将队列中的元素串联起来
			Node tmp = queue.get(0);
			for(int i=1;i<size;++i) {
				tmp.next = queue.get(i);
				tmp = queue.get(i);
			}
			//遍历队列中的每个元素，将每个元素的左右节点也放入队列中
			for(int i=0;i<size;++i) {
				tmp = queue.remove();
				if(tmp.left!=null) {
					queue.add(tmp.left);
				}
				if(tmp.right!=null) {
					queue.add(tmp.right);
				}
			}
		}
		return root;
	}
}

python代码:

class Solution(object):
	def connect(self, root):
		"""
		:type root: Node
		:rtype: Node
		"""
		if not root:
			return root
		queue = [root]
		while queue:
			size = len(queue)
			# 将队列中的元素串联起来
			tmp = queue[0]
			for i in xrange(1,size):
				tmp.next = queue[i]
				tmp = queue[i]
			# 遍历队列中的每个元素，将每个元素的左右节点也放入队列中
			for _ in xrange(size):
				tmp = queue.pop(0)
				if tmp.left:
					queue.append(tmp.left)
				if tmp.right:
					queue.append(tmp.right)
		return root

迭代解法2

题目要求是常量的辅助空间，所以第一种解法并不符合要求，下面来看下O(1)空间复杂度的实现细节。
注意，题目说的二叉树是一棵完美二叉树，即每一层的节点都是满的。
仔细看下完成后的串联树，其连接的方式有两种:
第一种是这两个串联的节点都有一个共同的父节点，通过父节点就可以将这两个子节点串联起来

第二种是这两个串联的节点的父节点不同，对于这种情况，如果我们能将这一层的上一层串联好。那么可以通过父节点的next找到邻居，完成串联。

即

root.right.next => root.next.left

这里我们需要保证root.next不为空就可以了。
也就是说当我们要串联第i层节点时，需要先完成第i-1层的节点串联
第一层最多只有一个节点，不需要串联
第二层最多只有两个节点，借助根节点就可以完成串联了
第三层串联时，上一层已经串联完了，所以第三层可以完成串联
同理，可以完成第四层，第五层，第N层的串联

时间复杂度:O(n)
空间复杂度:O(1)

java代码

class Solution {
	public Node connect(Node root) {
		if(root==null) {
			return root;
		}
		Node pre = root;
		//循环条件是当前节点的left不为空，当只有根节点
		//或所有叶子节点都出串联完后循环就退出了
		while(pre.left!=null) {
			Node tmp = pre;
			while(tmp!=null) {
				//将tmp的左右节点都串联起来
				//注:外层循环已经判断了当前节点的left不为空
				tmp.left.next = tmp.right;
				//下一个不为空说明上一层已经帮我们完成串联了
				if(tmp.next!=null) {
					tmp.right.next = tmp.next.left;
				}
				//继续右边遍历
				tmp = tmp.next;
			}
			//从下一层的最左边开始遍历
			pre = pre.left;
		}
		return root;
	}
}

python代码:

class Solution(object):
	def connect(self, root):
		"""
		:type root: Node
		:rtype: Node
		"""
		if not root:
			return root
		pre = root
		# 循环条件是当前节点的left不为空，当只有根节点
		# 或所有叶子节点都出串联完后循环就退出了
		while pre.left:
			tmp = pre
			while tmp:
				# 将tmp的左右节点都串联起来
				# 注:外层循环已经判断了当前节点的left不为空
				tmp.left.next = tmp.right
				# 下一个不为空说明上一层已经帮我们完成串联了
				if tmp.next:
					tmp.right.next = tmp.next.left
				# 继续右边遍历
				tmp = tmp.next
			# 从下一层的最左边开始遍历	
			pre = pre.left
		return root

递归

上面两种方式是属于横向的视角，而递归则像是一个深度的视角。
以从上往下的方向看，1，2，3，5，6这几个节点在位置上都是紧挨着的，同时这几个节点都是左右串联的。

我们以当前节root点为起始，左右节点不断的深入下面，left节点不断往右走，right节点不断往左走，当这两个节点走到底后，整个纵深这段就完成了串联。
递归函数实现如下：

  1. 终止条件:当前节点为空时
  2. 函数内:以当前节点为起始，完成从上往下的纵深串联，再递归的调用当前left和right

时间复杂度:O(n)
空间复杂度:O(h)，h是树的高度

java代码:

class Solution {
	public Node connect(Node root) {
		dfs(root);
		return root;
	}
	
	void dfs(Node root) {
		if(root==null) {
			return;
		}
		Node left = root.left;
		Node right = root.right;
		//配合动画演示理解这段，以root为起点，将整个纵深这段串联起来
		while(left!=null) {
			left.next = right;
			left = left.right;
			right = right.left;
		}
		//递归的调用左右节点，完成同样的纵深串联
		dfs(root.left);
		dfs(root.right);
	}
}

python代码:

class Solution(object):
	def connect(self, root):
		"""
		:type root: Node
		:rtype: Node
		"""
		def dfs(root):
			if not root:
				return
			left = root.left
			right = root.right
			# 配合动画演示理解这段，以root为起点，将整个纵深这段串联起来
			while left:
				left.next = right
				left = left.right
				right = right.left
			# 递归的调用左右节点，完成同样的纵深串联
			dfs(root.left)
			dfs(root.right)
		dfs(root)
		return root

(全文完)

5 次阅读

发表评论

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