Recursive algorithm traversal

Public static int[] preTraversalTree(TreeNode rootNode) {ArrayList<Integer> ArrayList = new ArrayList<>(); preOrder(rootNode, arrayList); return arrayList.stream().mapToInt(Integer::intValue).toArray(); } /** * public static void preOrder(TreeNode rootNode, ArrayList<Integer> list) { if (rootNode == null) { return; } list.add(rootNode.val); preOrder(rootNode.left, list); preOrder(rootNode.right, list); } public static int[] inTraversalTree(TreeNode rootNode) { ArrayList<Integer> arrayList = new ArrayList<>(); inOrder(rootNode, arrayList); return arrayList.stream().mapToInt(Integer::intValue).toArray(); } public static void inOrder(TreeNode rootNode, TreeNode rootNode, ArrayList<Integer> list) { if (rootNode == null) { return; } inOrder(rootNode.left, list); list.add(rootNode.val); inOrder(rootNode.right, list); } public static int[] postTraversalTree(TreeNode rootNode) {ArrayList<Integer> arrayList = new ArrayList<>(); postOrder(rootNode, arrayList); return arrayList.stream().mapToInt(Integer::intValue).toArray(); } @param rootNode @param list */ public static void postOrder(TreeNode rootNode, ArrayList<Integer> list) { if (rootNode == null) { return; } postOrder(rootNode.left, list); postOrder(rootNode.right, list); list.add(rootNode.val); }Copy the code

Iterative algorithm traversal

The former sequence traversal

Ideas and Algorithms

We can also implement the recursive function of method 1 iteratively. The two methods are equivalent, but the difference is that the recursion implicitly maintains a stack, while we need to simulate the stack explicitly during iteration. The rest of the implementation and details are the same, please refer to the following code.

,

public static List<Integer> preOrderTraverse(TreeNode rootNode) { Stack<TreeNode> stack = new Stack<>(); ArrayList<Integer> arrayList = new ArrayList<>(); while (rootNode ! = null || ! stack.isEmpty()) { while (rootNode ! = null) { arrayList.add(rootNode.val); stack.push(rootNode); rootNode = rootNode.left; } TreeNode pop = stack.pop(); rootNode = pop.right; } return arrayList; }Copy the code

After the sequence traversal

public static List<Integer> postOrderTraverse(TreeNode root) { List<Integer> res = new ArrayList<Integer>(); if (root == null) { return res; } Stack<TreeNode> stack = new Stack<>(); TreeNode prev = null; while (root ! = null || ! stack.isEmpty()) { while (root ! = null) { stack.push(root); root = root.left; } root = stack.pop(); if (root.right == null || root.right == prev) { res.add(root.val); prev = root; root = null; } else { stack.push(root); root = root.right; } } return res; }Copy the code

In the sequence traversal

Stack<TreeNode> stack = new Stack<>(); ArrayList<Integer> arrayList = new ArrayList<>(); while (root ! = null || ! stack.isEmpty()) { while (root ! = null) { stack.push(root); root = root.left; } root = stack.pop(); arrayList.add(root.val); root = root.right; } return arrayList;Copy the code

【 reference 】 [1] Leetcode