[Leetcode学习-java]Binary Tree Level Order Traversal & Binary Tree Level Order Traversal II(遍历二叉树)

自上而下遍历二叉树：

难度：easy

说明：

给一个二叉树，然后把从上到下遍历数值，返回一个结果List。

问题链接：https://leetcode.com/problems/binary-tree-level-order-traversal/

输入案例：

3 / \ 9 20 / \ 15 7 return its level order traversal as: [ [3], [9,20], [15,7] ]

我的代码：

从上而下遍历，BSF就行了，然后用滚动数组(也可以理解为双栈)，进行结果集存放（编译原理里面对DFA状态处理也是如此），结果集用尾插法。

class Solution { // 静态化，在测试调用时候会更快 static int top01 = 0; static int top02 = 0; // 省时间用了滚动数组(也可以理解为双栈) static int cur = 0; static int pre = 1; static TreeNode[][] stack = new TreeNode[2][1000]; public List<List<Integer>> levelOrder(TreeNode root) { List<Integer> list = new ArrayList<>(); List<List<Integer>> res = new LinkedList<List<Integer>>(); if(root != null) { list.add(root.val); stack[cur][top01 ++] = root; } while(top01 != 0) { cur ^= 1; pre ^= 1; // 尾插法 res.add(list); list = new ArrayList<>(); for(int i = 0;i < top01;i ++) { TreeNode node = stack[pre][i]; if(node.left != null) { stack[cur][top02 ++] = node.left; list.add(node.left.val); } if(node.right != null) { stack[cur][top02 ++] = node.right; list.add(node.right.val); } } top01 = top02; top02 = 0; } return res; } }

---

自下而上遍历二叉树：

难度：easy

说明：

给一个二叉树，然后把自下而上（颠倒）遍历数值，返回一个结果List。

问题链接：https://leetcode.com/problems/binary-tree-level-order-traversal-ii/

输入案例：

3 / \ 9 20 / \ 15 7 return its bottom-up level order traversal as: [ [15,7], [9,20], [3] ]

我的代码：

算法和上面的没什么不同，只是结果集那里用头插法。

class Solution { static int top01 = 0; static int top02 = 0; static int cur = 0; static int pre = 1; static TreeNode[][] stack = new TreeNode[2][1000]; public List<List<Integer>> levelOrderBottom(TreeNode root) { List<Integer> stack03 = new ArrayList<Integer>(); List<List<Integer>> res = new ArrayList<List<Integer>>(); if(root != null) { stack[cur][top01 ++] = root; stack03.add(root.val); } while(top01 != 0) { cur ^= 1; pre ^= 1; // 进行头插法 res.add(0,stack03); stack03 = new ArrayList<>(); for(int i = 0;i < top01;i ++) { TreeNode node = stack[pre][i]; if(node.left != null) { stack[cur][top02 ++] = node.left; stack03.add(node.left.val); } if(node.right != null) { stack[cur][top02 ++] = node.right; stack03.add(node.right.val); } } top01 = top02; top02 = 0; } return res; } }