refer to: https://www.algoexpert.io/questions/BST%20Traversal && leetcode &&力扣
分别使用前序遍历中序遍历后序遍历的方法遍历搜索二叉树
1 import java.util.*; 2 3 class Program { 4 public static List<Integer> inOrderTraverse(BST tree, List<Integer> array) { 5 if(tree.left != null){ 6 inOrderTraverse(tree.left, array); 7 } 8 array.add(tree.value); 9 if(tree.right != null){ 10 inOrderTraverse(tree.right, array); 11 } 12 return array; 13 } 14 15 public static List<Integer> preOrderTraverse(BST tree, List<Integer> array) { 16 array.add(tree.value); 17 if(tree.left != null){ 18 preOrderTraverse(tree.left, array); 19 } 20 if(tree.right != null){ 21 preOrderTraverse(tree.right, array); 22 } 23 return array; 24 } 25 26 public static List<Integer> postOrderTraverse(BST tree, List<Integer> array) { 27 if(tree.left != null){ 28 postOrderTraverse(tree.left, array); 29 } 30 if(tree.right != null){ 31 postOrderTraverse(tree.right, array); 32 } 33 array.add(tree.value); 34 return array; 35 } 36 37 static class BST { 38 public int value; 39 public BST left; 40 public BST right; 41 42 public BST(int value) { 43 this.value = value; 44 } 45 } 46 }
1 def inOrderTraverse(tree, array): 2 # Write your code here. 3 if tree is not None: 4 inOrderTraverse(tree.left, array) 5 array.append(tree.value) 6 inOrderTraverse(tree.right, array) 7 return array 8 9 10 def preOrderTraverse(tree, array): 11 # Write your code here. 12 if tree is not None: 13 array.append(tree.value) 14 preOrderTraverse(tree.left, array) 15 preOrderTraverse(tree.right, array) 16 return array 17 18 19 def postOrderTraverse(tree, array): 20 # Write your code here. 21 if tree is not None: 22 postOrderTraverse(tree.left, array) 23 postOrderTraverse(tree.right, array) 24 array.append(tree.value) 25 return array
refer to : leedcode && 力扣
1 import java.util.*; 2 3 class Program { 4 public static List<Integer> inOrderTraverse(BST tree, List<Integer> array) { 5 6 Stack<BST> stack = new Stack<>(); 7 if(tree == null) return array; 8 BST cur = tree; 9 while(cur != null || !stack.isEmpty()){ 10 while(cur != null){ 11 stack.push(cur); 12 cur = cur.left; 13 } 14 15 cur = stack.pop(); 16 array.add(cur.value); 17 cur = cur.right; 18 } 19 return array; 20 } 21 22 public static List<Integer> preOrderTraverse(BST tree, List<Integer> array) { 23 Stack<BST> stack = new Stack<>(); 24 if(tree == null) return array; 25 stack.push(tree); 26 while(!stack.isEmpty()){ 27 BST node = stack.pop(); 28 array.add(node.value); 29 if(node.right != null){ 30 stack.push(node.right); 31 } 32 if(node.left != null){ 33 stack.push(node.left); 34 } 35 } 36 return array; 37 }
--why push node.right first, node,left later? --stack property: first in last out, so last left in, first left out. 38 39 public static List<Integer> postOrderTraverse(BST tree, List<Integer> array) { 40 Stack<BST> s = new Stack<>(); 41 Set<BST> seen = new HashSet<>(); 42 while (tree != null || !s.isEmpty()) { 43 if (tree == null && seen.contains(s.peek())) { 44 array.add(s.pop().value); 45 } 46 else if (tree == null) { //step2: 达到了left most,seen.add(left_most node) 47 seen.add(s.peek()); 48 tree = s.peek().right; //tree=left_most node的右孩子 49 } 50 else { //step1 ： tree == null，程序的开始进入这一步,左孩子全部加进栈，直到达到left most node 51 s.push(tree); 52 tree = tree.left; 53 } 54 } 55 return array; 56 } 57 58 static class BST { 59 public int value; 60 public BST left; 61 public BST right; 62 63 public BST(int value) { 64 this.value = value; 65 } 66 } 67 }
time cpmplexity: O(N). || space complexity: O(N)