实现二叉树先,中,后序遍历
实现二叉树先序,中序和后序遍历
http://www.nowcoder.com/questionTerminal/a9fec6c46a684ad5a3abd4e365a9d362
思路:
先,中,后遍历存到一个集合里,然后遍历集合填充数组,数组列长度需在第一次先序遍历后计算,也可以最后集合长度除以3获得;
public class Solution { /** * * @param root TreeNode类 the root of binary tree * @return int整型二维数组 */ public int[][] threeOrders (TreeNode root) { // write code here // 先序遍历 ArrayList<Integer> list = new ArrayList(); preorder(root, list); int m = list.size(); int[][] arr = new int[3][m]; inorder(root, list); postorder(root, list); int k = 0; for(int i = 0; i<3; i++){ for(int j = 0; j<m; j++){ arr[i][j] = list.get(k++); } } return arr; } private void preorder(TreeNode root, ArrayList<Integer> list){ if( root == null){ return ; } list.add(root.val); preorder(root.left, list); preorder(root.right,list); } private void inorder(TreeNode root, ArrayList<Integer> list){ if(root == null){ return ; } inorder(root.left, list); list.add(root.val); inorder(root.right, list); } private void postorder(TreeNode root, ArrayList<Integer> list){ if(root == null){ return ; } postorder(root.left, list); postorder(root.right, list); list.add(root.val); } }