递归最简略，迭代要用栈（其实也是模仿递归）。
前序遍历
递归
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */class Solution { List<Integer> res = new ArrayList<Integer>(); public List<Integer> preorderTraversal(TreeNode root) { if(root == null) return res; res.add(root.val); preorderTraversal(root.left); preorderTraversal(root.right); return res; }}
迭代
class Solution { List<Integer> res = new ArrayList<Integer>(); Stack<TreeNode> stack = new Stack<TreeNode>(); public List<Integer> preorderTraversal(TreeNode root) { if(root == null) return res; //前序根节点间接拜访 stack.push(root); while(!stack.isEmpty()) { TreeNode cur = stack.pop(); res.add(cur.val); if(cur.right != null) { stack.push(cur.right); } if(cur.left != null) { stack.push(cur.left); } } return res; }}
中序遍历
递归
class Solution { List<Integer> res = new ArrayList<Integer>(); public List<Integer> inorderTraversal(TreeNode root) { if(root == null) return res; inorderTraversal(root.left); res.add(root.val); inorderTraversal(root.right); return res; }}
迭代
class Solution { List<Integer> res = new ArrayList<Integer>(); Stack<TreeNode> stack = new Stack<TreeNode>(); public List<Integer> inorderTraversal(TreeNode root) { if(root == null) return res; //中序 左-根-右 while(root != null || !stack.isEmpty()) { //根节点不空就间接压栈 if(root != null) { stack.push(root); root = root.left; }else{ //根节点为空出栈间接拜访左节点 root = stack.pop(); res.add(root.val); root = root.right; } } return res; }}
后序遍历
递归
class Solution { List<Integer> res = new ArrayList<Integer>(); public List<Integer> postorderTraversal(TreeNode root) { if(root == null) return res; postorderTraversal(root.left); postorderTraversal(root.right); res.add(root.val); return res; }}
迭代
class Solution { LinkedList<Integer> res = new LinkedList<Integer>(); Stack<TreeNode> stack = new Stack<TreeNode>(); public List<Integer> postorderTraversal(TreeNode root) { if(root == null) return res; //根节点最初拜访先入栈 stack.push(root); while(!stack.isEmpty()) { TreeNode cur = stack.pop(); res.addFirst(cur.val); if(cur.left != null) { stack.push(cur.left); } if(cur.right != null) { stack.push(cur.right); } } return res; }}