数据结构_树_遍历

树的遍历

例题一

请用递归方式实现二叉树的先序、中序和后序的遍历打印。

给定一个二叉树的根结点root，请依次返回二叉树的先序，中序和后续遍历(二维数组的形式)。

import java.util.*;/*
public class TreeNode {int val = 0;TreeNode left = null;TreeNode right = null;public TreeNode(int val) {this.val = val;}
}*/
public class TreeToSequence {public int[][] convert(TreeNode root) {// write code hereList<Integer> pre = new ArrayList<Integer>();List<Integer> in = new ArrayList<Integer>();List<Integer> post = new ArrayList<Integer>();preTraverse(root, pre);inTraverse(root, in);postTraverse(root, post);int[][] result = new int[3][pre.size()];for(int i = 0; i < pre.size(); i++){result[0][i] = pre.get(i);result[1][i] = in.get(i);result[2][i] = post.get(i);}return result;}public void preTraverse(TreeNode root, List<Integer> pre){if(root == null){return ;}pre.add(root.val);preTraverse(root.left, pre);preTraverse(root.right, pre);}public void inTraverse(TreeNode root, List<Integer> in){if(root == null){return ;}inTraverse(root.left, in);in.add(root.val);inTraverse(root.right, in);}public void postTraverse(TreeNode root, List<Integer> post){if(root == null){return ;}postTraverse(root.left, post);postTraverse(root.right, post);post.add(root.val);}
}

非递归遍历

import java.util.*;/*
public class TreeNode {int val = 0;TreeNode left = null;TreeNode right = null;public TreeNode(int val) {this.val = val;}
}*/
public class TreeToSequence {public int[][] convert(TreeNode root) {// write code here// write code hereList<Integer> pre = new ArrayList<Integer>();List<Integer> in = new ArrayList<Integer>();List<Integer> post = new ArrayList<Integer>();preTraverse(root, pre);inTraverse(root, in);postTraverse(root, post);int[][] result = new int[3][pre.size()];for(int i = 0; i < pre.size(); i++){result[0][i] = pre.get(i);result[1][i] = in.get(i);result[2][i] = post.get(i);}return result;}public void preTraverse(TreeNode root, List<Integer> pre){if(root == null){return;}Stack<TreeNode> stack = new Stack<TreeNode>();stack.push(root);while(!stack.isEmpty()){TreeNode cur = stack.pop();pre.add(cur.val);if(cur.right != null){stack.push(cur.right);}if(cur.left != null){stack.push(cur.left);}}}public void inTraverse(TreeNode root, List<Integer> in){if(root == null){return;}Stack<TreeNode> stack = new Stack<TreeNode>();TreeNode cur = root;while(!stack.isEmpty() || cur != null){if(cur!= null){stack.push(cur);cur = cur.left;}else{cur = stack.pop();in.add(cur.val);cur = cur.right;}}}public void postTraverse(TreeNode root, List<Integer> post){if(root == null){return;}Stack<TreeNode> stack1 = new Stack<TreeNode>();Stack<TreeNode> stack2 = new Stack<TreeNode>();stack1.push(root);while(!stack1.isEmpty()){TreeNode cur = stack1.pop();stack2.push(cur);if(cur.left != null){stack1.push(cur.left);}if(cur.right != null){stack1.push(cur.right);}}while(!stack2.isEmpty()){post.add(stack2.pop().val);}}
}