Middle order Traversal of binary trees (iteration + recursion)

• Iterative method

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
       List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        while(root ! = null || ! stack.isEmpty()) {while(root ! = null) { stack.push(root); root = root.left; } root = stack.pop(); list.add(root.val); root = root.right; }returnlist; }}Copy the code

• The recursive method

class Solution { private List<Integer> ans = new ArrayList<>(); Public List<Integer> inorderTraversal(TreeNode root) {DFS (root);return ans;
    }
     private void dfs(TreeNode root) {
        if (root == null) return; dfs(root.left); ans.add(root.val); dfs(root.right); }}Copy the code