LEETCODE 94. 二叉树的中序遍历

LEETCODE 94. 二叉树的中序遍历

题解

给定一个二叉树,返回它的中序 遍历。
示例:
输入: [1,null,2,3]

   1
    \
     2
    /
   3

输出: [1,3,2]
进阶: 递归算法很简单,你可以通过迭代算法完成吗?

题目地址:

https://leetcode-cn.com/problems/binary-tree-inorder-traversal/

递归实现

递归遍历太简单了

  • 前序遍历:打印-左-右
  • 中序遍历:左-打印-右
  • 后序遍历:左-右-打印

题目要求的是中序遍历,那就按照 左-打印-右这种顺序遍历树就可以了,递归函数实现

  1. 终止条件:当前节点为空时
  2. 函数内: 递归的调用左节点,打印当前节点,再递归调用右节点

时间复杂度:O(n)
空间复杂度:O(h),h是树的高度
java代码:

class Solution {
	public List<Integer> inorderTraversal(TreeNode root) {
		List<Integer> res = new ArrayList<Integer>();
		dfs(res,root);
		return res;
	}
	
	void dfs(List<Integer> res, TreeNode root) {
		if(root==null) {
			return;
		}
		//按照 左-打印-右的方式遍历
		dfs(res,root.left);
		res.add(root.val);
		dfs(res,root.right);
	}
}
                                                                    

python代码:

class Solution(object):
	def inorderTraversal(self, root):
		"""
		:type root: TreeNode
		:rtype: List[int]
		"""
		res = []
		def dfs(root):
			if not root:
				return
			# 按照 左-打印-右的方式遍历	
			dfs(root.left)
			res.append(root.val)
			dfs(root.right)
		dfs(root)
		return res
                                                       

迭代实现

这题的真正难点在于如何用非递归的方式实现。
递归实现时,是函数自己调用自己,一层层的嵌套下去,操作系统/虚拟机自动帮我们用来保存了每个调用的函数,现在我们需要自己模拟这样的调用过程。
递归的调用过程是这样的:

dfs(root.left)
	dfs(root.left)
		dfs(root.left)
			为null返回
		打印节点
		dfs(root.right)
			dfs(root.left)
				dfs(root.left)
				........
				   

递归的调用过程是不断往左边走,当左边走不下去了,就打印节点,并转向右边,然后右边继续这个过程。
我们在迭代实现时,就可以用栈来模拟上面的调用过程。

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

java代码:

class Solution {
	public List<Integer> inorderTraversal(TreeNode root) {
		List<Integer> res = new ArrayList<Integer>();
		Stack<TreeNode> stack = new Stack<TreeNode>();
		while(stack.size()>0 || root!=null) {
			//不断往左子树方向走,每走一次就将当前节点保存到栈中
			//这是模拟递归的调用
			if(root!=null) {
				stack.add(root);
				root = root.left;
			//当前节点为空,说明左边走到头了,从栈中弹出节点并保存
			//然后转向右边节点,继续上面整个过程
			} else {
				TreeNode tmp = stack.pop();
				res.add(tmp.val);
				root = tmp.right;
			}
		}
		return res;
	}
}
                                                                                

python代码:

class Solution(object):
	def inorderTraversal(self, root):
		"""
		:type root: TreeNode
		:rtype: List[int]
		"""
		res = []
		stack = []
		while stack or root:
			# 不断往左子树方向走,每走一次就将当前节点保存到栈中
			# 这是模拟递归的调用
			if root:
				stack.append(root)
				root = root.left
			# 当前节点为空,说明左边走到头了,从栈中弹出节点并保存
			# 然后转向右边节点,继续上面整个过程
			else:
				tmp = stack.pop()
				res.append(tmp.val)
				root = tmp.right
		return res
                                                                                

莫里斯遍历

用递归和迭代的方式都使用了辅助的空间,而莫里斯遍历的优点是没有使用任何辅助空间。
缺点是改变了整个树的结构,强行把一棵二叉树改成一段链表结构。

我们将黄色区域部分挂到节点5的右子树上,接着再把25这两个节点挂到4节点的右边。
这样整棵树基本上就变改成了一个链表了,之后再不断往右遍历。

时间复杂度:找到每个前驱节点的复杂度是O(n),因为n个节点的二叉树有n-1条边,每条边只可能使用2次(一次定位到节点,一次找到前驱节点),故时间复杂度为O(n)

空间复杂度:O(1)

class Solution {
	public List<Integer> inorderTraversal(TreeNode root) {
		List<Integer> res = new ArrayList<Integer>();
		TreeNode pre = null;
		while(root!=null) {
			//如果左节点不为空,就将当前节点连带右子树全部挂到
			//左节点的最右子树下面
			if(root.left!=null) {
				pre = root.left;
				while(pre.right!=null) {
					pre = pre.right;
				}
				pre.right = root;
				//将root指向root的left
				TreeNode tmp = root;
				root = root.left;
				tmp.left = null;
			//左子树为空,则打印这个节点,并向右边遍历	
			} else {
				res.add(root.val);
				root = root.right;
			}
		}
		return res;
	}
}
                                                                               

python代码:

class Solution(object):
	def inorderTraversal(self, root):
		"""
		:type root: TreeNode
		:rtype: List[int]
		"""
		res = []
		pre = None
		while root:
			# 如果左节点不为空,就将当前节点连带右子树全部挂到
			# 左节点的最右子树下面
			if root.left:
				pre = root.left
				while pre.right:
					pre = pre.right
				pre.right = root
				# 将root指向root的left
				tmp = root
				root = root.left
				tmp.left = None
			# 左子树为空,则打印这个节点,并向右边遍历	
			else:
				res.append(root.val)
				root = root.right
		return res
                                                                        

(全文完)

9 次阅读

发表评论

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