二叉树学习——前序、中序、后序遍历（Java实现）

一些学习总结

递归实现:

1.前序遍历 public static ArrayList<Integer> preorderTraversal(TreeNode root) { ArrayList<Integer> sort = new ArrayList<>(); if (root == null) { return sort; } if (root.left == null && root.right == null) { sort.add(root.val); return sort; } sort.add(root.val); sort.addAll(preorderTraversal(root.left)); sort.addAll(preorderTraversal(root.right)); return sort; } 2.中序遍历 public static ArrayList<Integer> inorderTraversal(TreeNode root) { ArrayList<Integer> sort = new ArrayList<>(); if (root == null) { return sort; } if (root.left == null && root.right == null) { sort.add(root.val); return sort; } sort.addAll(inorderTraversal(root.left)); sort.add(root.val); sort.addAll(inorderTraversal(root.right)); return sort; } 3.后序遍历 public static ArrayList<Integer> postorderTraversal(TreeNode root) { ArrayList<Integer> sort = new ArrayList<>(); if (root == null) { return sort; } if (root.left == null && root.right == null) { sort.add(root.val); return sort; } sort.addAll(postorderTraversal(root.left)); sort.addAll(postorderTraversal(root.right)); sort.add(root.val); return sort; }

非递归实现

4. 前序遍历 public static ArrayList<Integer> preorderTraversal(TreeNode root) { ArrayList<Integer> sort = new ArrayList<>(); TreeNode cur = root; Stack<TreeNode> stack = new Stack<>(); while (cur != null || !stack.isEmpty()) { while (cur != null) { sort.add(cur.val); stack.push(cur); cur = cur.left; } cur = stack.pop(); cur = cur.right; } return sort; } 5.中序遍历 public static ArrayList<Integer> inorderTraversal(TreeNode root) { ArrayList<Integer> sort = new ArrayList<>(); TreeNode cur = root; Stack<TreeNode> stack = new Stack<>(); while (cur != null || !stack.isEmpty()) { while (cur != null) { stack.push(cur); cur = cur.left; } cur = stack.pop(); sort.add(cur.val); cur = cur.right; } return sort; } 6.后序遍历 public static ArrayList<Integer> postorderTraversal(TreeNode root) { ArrayList<Integer> sort = new ArrayList<>(); Stack<TreeNode> stack = new Stack<>(); Stack<TreeNode> stack2 = new Stack<>(); TreeNode cur = root; while (cur != null || !stack.isEmpty()) { while (cur != null) { stack.push(cur); stack2.push(cur); cur = cur.right; } cur = stack.pop(); cur = cur.left; } sort.add(stack2.pop().val); while (stack2.size() > 0) { cur = stack2.pop(); sort.add(cur.val); } return sort; }