leetcode-11-二叉树前中后序遍历以及层次遍历

一、递归版

前序遍历 （先根遍历） 中左右

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

中序遍历 左中右

后序遍历 左右中

二、迭代版

// 前序遍历顺序：中-左-右，入栈顺序：中-右-左
class Solution {public List<Integer> preorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<>();if (root == null){return result;}Stack<TreeNode> stack = new Stack<>();stack.push(root);while (!stack.isEmpty()){TreeNode node = stack.pop();result.add(node.val);if (node.right != null){stack.push(node.right);}if (node.left != null){stack.push(node.left);}}return result;}
}// 中序遍历顺序: 左-中-右 入栈顺序： 左-右
class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<>();if (root == null){return result;}Stack<TreeNode> stack = new Stack<>();TreeNode cur = root;while (cur != null || !stack.isEmpty()){if (cur != null){stack.push(cur);cur = cur.left;}else{cur = stack.pop();result.add(cur.val);cur = cur.right;}}return result;}
}// 后序遍历顺序 左-右-中 入栈顺序：中-左-右 出栈顺序：中-右-左， 最后翻转结果
class Solution {public List<Integer> postorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<>();if (root == null){return result;}Stack<TreeNode> stack = new Stack<>();stack.push(root);while (!stack.isEmpty()){TreeNode node = stack.pop();result.add(node.val);if (node.left != null){stack.push(node.left);}if (node.right != null){stack.push(node.right);}}Collections.reverse(result);return result;}
}

三、层次遍历

[102]二叉树的层次遍历

重点：使用队列

class Solution {public List<List<Integer>> levelOrder(TreeNode root) {List<List<Integer>> res=new ArrayList<>();LinkedList<TreeNode> queue=new LinkedList<>();if(root==null) return res;queue.offer(root);while(!queue.isEmpty()){int size= queue.size();List<Integer> tmp=new ArrayList<>();while(size>0){TreeNode node=queue.poll();tmp.add(node.val);if(node.left!=null){queue.offer(node.left);}if(node.right!=null){queue.offer(node.right);}size--;}res.add(tmp);}return res;}
}

 [102]、[107]、[199]、[637]、[429]、[515]、[116]、[117]、[104]、[111]

10题解法类似，均可采用层次遍历的思想