剑指offer

2018-3-13

请实现一个函数按照之字形打印二叉树

1 思路：两个栈

View Code

 1 import java.util.*;
 2 
 3 /*
 4 public class TreeNode {
 5     int val = 0;
 6     TreeNode left = null;
 7     TreeNode right = null;
 8 
 9     public TreeNode(int val) {
10         this.val = val;
11 
12     }
13 
14 }
15 */
16 public class Solution {
17     public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
18         ArrayList<ArrayList<Integer>> res = new ArrayList<>();
19         if (pRoot == null) {
20             return res;
21         }
22         Stack<TreeNode> stack1 = new Stack<>();
23         Stack<TreeNode> stack2 = new Stack<>();
24         stack1.push(pRoot);
25         while (!stack1.isEmpty() || !stack2.isEmpty()) {
26             ArrayList<Integer> layer = new ArrayList<>();
27             while (!stack1.isEmpty()) {
28                 TreeNode node = stack1.pop();
29                 layer.add(node.val);
30                 if (node.left != null) {
31                     stack2.push(node.left);
32                 }
33                 if (node.right != null) {
34                     stack2.push(node.right);
35                 }
36             }
37             res.add(layer);
38             layer = new ArrayList<>();
39             while (!stack2.isEmpty()) {
40                 TreeNode node = stack2.pop();
41                 layer.add(node.val);
42                 if (node.right != null) {
43                     stack1.push(node.right);
44                 }
45                 if (node.left != null) {
46                     stack1.push(node.left);
47                 }
48             }
49             if (!layer.isEmpty()) {
50                 res.add(layer);
51             }
52         }
53         return res;
54     }
55 
56 }

View Code

把二叉树打印成多行：从上到下按

 1 import java.util.ArrayList;
 2 
 3 
 4 /*
 5 public class TreeNode {
 6     int val = 0;
 7     TreeNode left = null;
 8     TreeNode right = null;
 9 
10     public TreeNode(int val) {
11         this.val = val;
12 
13     }
14 
15 }
16 */
17 public class Solution {
18     ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
19     
20     }
21     
22 }

View Code

层打印二叉树，同一层结点从左至右输出。每一层输出一行。