一、递归版
前/中/后 指的是访问根结点的次序
前序遍历 (先根遍历) 中左右
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题解法类似,均可采用层次遍历的思想