首页 > 其他 > 详细

SpiralOrderTraverse,螺旋遍历二叉树,利用两个栈

时间:2016-06-28 21:45:32      阅读:277      评论:0      收藏:0      [点我收藏+]

问题描述:s型遍历二叉树,或者反s型遍历二叉树

算法分析:层序遍历二叉树只需要一个队列,因为每一层都是从左往右遍历,而s型遍历二叉树就要用两个栈了,因为每次方向相反。

public static void SpiralOrderTraverse(TreeNode t) {
		Stack<TreeNode> stack1 = new Stack<>();
		Stack<TreeNode> stack2 = new Stack<>();
		stack1.push(t);
		while (!stack1.isEmpty() || !stack2.isEmpty()) {
			while (!stack1.isEmpty()) {
				TreeNode tn = stack1.pop();
				System.out.print(tn.val + " ");
				if (tn.right != null) {
					stack2.push(tn.right);
				}
				if (tn.left != null) {
					stack2.push(tn.left);
				}
			}
			while (!stack2.isEmpty()) {
				TreeNode tn = stack2.pop();
				System.out.print(tn.val + " ");
				if (tn.left != null) {
					stack1.push(tn.left);
				}
				if (tn.right != null) {
					stack1.push(tn.right);
				}
			}
		}
	}

 

SpiralOrderTraverse,螺旋遍历二叉树,利用两个栈

原文:http://www.cnblogs.com/masterlibin/p/5624975.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!