94. 二叉树的中序遍历-M

解法1-递归

class Solution { List<Integer> res = new ArrayList<>(); public List<Integer> inorderTraversal(TreeNode root) { if (root == null){ return res; } inorderTraversal(root.left); res.add(root.val); inorderTraversal(root.right); return res; } }

解法2-非递归，栈-显示递归

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

144. 二叉树的前序遍历-M

解法1-递归

class Solution { List<Integer> res = new ArrayList<>(); public List<Integer> preorderTraversal(TreeNode root) { if (root == null){ return res; } res.add(root.val); preorderTraversal(root.left); preorderTraversal(root.right); return res; } }

解法2-非递归

class Solution { public List<Integer> preorderTraversal(TreeNode root) { List<Integer> res = new ArrayList<>(); Stack<TreeNode> stack = new Stack<>(); while (root != null || !stack.isEmpty()){ while (root != null){ res.add(root.val); stack.push(root); root = root.left; } root = stack.pop(); root = root.right; } return res; } }

145. 二叉树的后序遍历

解法1-递归

class Solution { List<Integer> res = new ArrayList<>(); public List<Integer> postorderTraversal(TreeNode root) { if (root == null){ return res; } postorderTraversal(root.left); postorderTraversal(root.right); res.add(root.val); return res; } }

解法2-非递归-Hard !

class Solution { public List<Integer> postorderTraversal(TreeNode root) { List<Integer> res = new ArrayList<Integer>(); if (root == null) { return res; } Deque<TreeNode> stack = new LinkedList<TreeNode>(); 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; } }