常考数据结构与算法:二叉树的之字形层序遍历

题目描述

给定一个二叉树，返回该二叉树的之字形层序遍历，（第一层从左向右，下一层从右向左，一直这样交替）
例如：
给定的二叉树是{3,9,20,#,#,15,7},

该二叉树之字形层序遍历的结果是

[

[3],

[20,9],

[15,7]

]

示例1

输入

{1,#,2}

返回值

[[1],[2]]

 

   二叉树遍历，脑海中立刻想到的就是深度优先遍历和广度优先遍历，这两种方式相信大家都驾轻就熟了，就不再过多累赘。

import java.util.ArrayList; import java.util.Stack;public class ZigzagLevelOrderMe {public static void main(String[]args){//System.out.println("Hello Wolrd!");TreeNode root=new TreeNode(3);root.left=new TreeNode(9);root.right=new TreeNode(20);root.right.left=new TreeNode(15);root.right.right=new TreeNode(7);ZigzagLevelOrderMe s=new ZigzagLevelOrderMe();System.out.println(s.zigzagLevelOrder(root));//s.loop(root);}/* 思路一用栈实现设两个栈，s2存放奇数层，s1存放偶数层遍历s2节点的同时按照左子树、右子树的顺序加入s1，遍历s1节点的同时按照右子树、左子树的顺序加入s2*/public ArrayList<ArrayList<Integer>> zigzagLevelOrder (TreeNode root) {ArrayList<ArrayList<Integer>> arr=new ArrayList<ArrayList<Integer>>();if(root==null)return arr;Stack<TreeNode> stack1 = new Stack();Stack<TreeNode> stack2 = new Stack();boolean isLeftToRight = true;stack1.push(root);while(!stack1.isEmpty() || !stack2.isEmpty()){ArrayList<Integer> temp = new ArrayList<>();if(isLeftToRight){while(!stack1.isEmpty()){TreeNode node = stack1.pop();temp.add(node.val);if(node.left != null){stack2.push(node.left);}if(node.right != null){stack2.push(node.right);}}}else{while(!stack2.isEmpty()){TreeNode node = stack2.pop();temp.add(node.val);if(node.right != null){stack1.push(node.right);}if(node.left != null){stack1.push(node.left);}}}if(!temp.isEmpty()){arr.add(temp);}isLeftToRight = !isLeftToRight;}return arr;}// 思路二// 第一层从左向右，下一层从右向左，一直这样交替//递归版实现二叉树的层次遍历(之字形遍历)public void zigzagLevelHelper2(TreeNode root,int level, ArrayList<ArrayList<Integer>> arr){if(root==null)return ;if(level==arr.size()){ArrayList<Integer>newlevelResult=new ArrayList<>();if(level%2==0) //偶数层newlevelResult.add(root.val);else //奇数层newlevelResult.add(0,root.val);arr.add(newlevelResult);}else{ArrayList<Integer>levelResult=arr.get(level);if(level%2==0)levelResult.add(root.val);elselevelResult.add(0,root.val);arr.set(level,levelResult);}//递归遍历左右节点zigzagLevelHelper2(root.left,level+1,arr);zigzagLevelHelper2(root.right,level+1,arr);}/*用栈实现设两个栈，s2存放奇数层，s1存放偶数层遍历s2节点的同时按照左子树、右子树的顺序加入s1，遍历s1节点的同时按照右子树、左子树的顺序加入s2*/ // public void loop(TreeNode root) { // if (root == null) return; // // ArrayList<TreeNode> res = new ArrayList<>(); // // Stack<TreeNode> stack1 = new Stack<>(); // Stack<TreeNode> stack2 = new Stack<>(); // boolean left2Right = true; // // stack1.push(root); // // while (!stack1.isEmpty() || !stack2.isEmpty()) { // // 从左向右 // if (left2Right) { // // while (!stack1.isEmpty()) { // TreeNode node = stack1.pop(); // res.add(node); // if (node.left != null) { // stack2.push(node.left); // } // if (node.right != null) { // stack2.push(node.right); // } // } // // 从右向左 // } else { // while (!stack2.isEmpty()) { // TreeNode node = stack2.pop(); // res.add(node); // if (node.right != null) { // stack1.push(node.right); // } // if (node.left != null) { // stack1.push(node.left); // } // } // } // // left2Right = !left2Right; // } // // for (TreeNode node : res) { // System.out.println("" + node.val); // } // }}

 

 

 

总结

以上是生活随笔为你收集整理的常考数据结构与算法:二叉树的之字形层序遍历的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。