首页 > 代码库 > 【leetcode】Binary Tree Zigzag Level Order Traversal

【leetcode】Binary Tree Zigzag Level Order Traversal

2024-07-12 22:19:37   219人阅读

Given a binary tree, return the zigzag level order traversal of its nodes‘ values. (ie, from left to right, then right to left for the next level and alternate between).

For example:
Given binary tree {3,9,20,#,#,15,7},

    3   /   9  20    /     15   7

return its zigzag level order traversal as:

[  [3],  [20,9],  [15,7]]

题解：首先设置一个变量zigZag表示在遍历下一层的时候，是否需要逆序，zigZag为true，表示下一层需要逆序，否则下一层不需要逆序。如果不需要逆序，那么在生成nextLevel的时候，先把这层节点的右子入栈，再把左子入栈；如果下一层需要逆序，先把这层节点的左子入栈，再把右子入栈。

比如最初zigZag = true（第二层需要逆序），在遍历第一层（根节点3）的时候，先把左子9入栈，再把右子20入栈，那么最后出栈时候得到的第二层遍历序列为[20,9]；然后zigZag=false（第三层不需要逆序），在遍历第二层的时候，先遍历20，将20右子入栈，然后将20的右子7放入nextLevel，再把左子15放入nextLevel，那么第三层出栈时实际得到[15,7]。

在这里有一点要注意，为什么不需要逆序的时候仍然需要用到栈呢？因为虽然当前层不需要逆序，但是当前层的上一层遍历的时候是逆序遍历的，所以仍然需要借助栈。比如如果我们把上述的树添加一个节点变成如下图所示的树：

    3   /   9  20 /  /  4  15   7

遍历第三层应该得到[4,15,7]，但是遍历第二层的顺序是20，9，所以20的孩子们还是要压到栈底，才能保证它们弹出来的时候在9的左子4的后面。

代码如下：

 1 /** 2  * Definition for binary tree 3  * public class TreeNode { 4  *     int val; 5  *     TreeNode left; 6  *     TreeNode right; 7  *     TreeNode(int x) { val = x; } 8  * } 9  */10 public class Solution {11     public List<List<Integer>> zigzagLevelOrder(TreeNode root) {12         List<List<Integer>> answer = new ArrayList<List<Integer>>();13         if(root == null)14             return answer;15         16         Stack<TreeNode> currLevel = new Stack<TreeNode>();17         Stack<TreeNode> nextLevel = new Stack<TreeNode>();18         boolean zigZag = true;19         20         currLevel.push(root);21         while(!currLevel.isEmpty()){22             ArrayList<Integer> result = new ArrayList<Integer>();23             24             while(!currLevel.isEmpty()){25                 TreeNode node = currLevel.pop();26                 result.add(node.val);27                 28                 if(!zigZag){29                     if(node.right != null)30                         nextLevel.push(node.right);31                     if(node.left != null)32                         nextLevel.push(node.left);33                 }34                 else {35                     if(node.left != null)36                         nextLevel.push(node.left);37                     if(node.right != null)38                         nextLevel.push(node.right);39                 }40             }41             42             zigZag = !zigZag;43             List<Integer> temp = new ArrayList<Integer>(result);44             answer.add(temp);45             result.clear();46             Stack<TreeNode> tmp = new Stack<TreeNode>();47             tmp.addAll(nextLevel);48             currLevel = tmp;49             nextLevel.clear();50         }51         return answer;52     }53 }

上述代码中46行的栈tmp是用来保存nextLevel栈的空间的，否则虽然把nextLevel栈赋值给currLevel了，但是当nextLevel清空的时候，这部分内存也会被清空，所以要把nextLevel中的元素放置到另一块内存里面。

栈的构造函数中不能直接把栈初始化成为另外一个栈，关于把一个栈赋值给另外一个栈的方法有很多，可以参见这里：http://stackoverflow.com/questions/7919836/how-do-i-copy-a-stack-in-java


联系
我们