递归遍历

LeetCode 144. 二叉树的前序遍历

题目链接：二叉树的前序遍历题目链接

代码

java">/*** 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 {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);}
}

LeetCode 145. 二叉树的后序遍历

题目链接：二叉树的后序遍历题目链接

代码

java">/*** 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 {public List<Integer> postorderTraversal(TreeNode root) {List<Integer>result=new ArrayList<Integer>();postorder(root,result);return result;}public void postorder(TreeNode root,List<Integer> result){if(root==null)return;postorder(root.left,result);postorder(root.right,result);result.add(root.val);}
}

LeetCode 94. 二叉树的中序遍历

题目链接：二叉树的中序遍历

代码

java">/*** 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 {public List<Integer> inorderTraversal(TreeNode root) {List<Integer>result=new ArrayList<Integer>();inorder(root,result);return result;}public void inorder(TreeNode root,List<Integer>result){if(root==null)return;inorder(root.left,result);result.add(root.val);inorder(root.right,result);}
}

迭代遍历

LeetCode 144. 二叉树的前序遍历

题目链接：二叉树的前序遍历题目链接

代码

java">/*** 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 {public List<Integer> preorderTraversal(TreeNode root) {Stack<TreeNode> stack=new Stack<>();List<Integer>result=new ArrayList<Integer>();if(root==null)return result;stack.push(root);while(!stack.isEmpty()){TreeNode node=stack.peek();stack.pop();result.add(node.val);if(node.right!=null) stack.push(node.right);if(node.left!=null) stack.push(node.left);}return result;}
}

LeetCode 94. 二叉树的中序遍历

题目链接：二叉树的中序遍历

代码

java">/*** 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 {public List<Integer> inorderTraversal(TreeNode root) {Stack<TreeNode>stack=new Stack<>();List<Integer>result=new ArrayList<>();TreeNode cur=root;while(cur!=null ||!stack.isEmpty()){if(cur!=null){stack.push(cur);cur=cur.left;}else{cur=stack.peek();stack.pop();result.add(cur.val);cur=cur.right;}}return result;}
}

LeetCode 145. 二叉树的后序遍历

题目链接：二叉树的后序遍历题目链接

代码

java">/*** 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 {public List<Integer> postorderTraversal(TreeNode root) {List<Integer> result=new ArrayList<>();Stack<TreeNode> stack=new Stack<>();if(root==null)return result;stack.push(root);while(!stack.isEmpty()){TreeNode cur=stack.peek();stack.pop();result.add(cur.val);if(cur.left!=null)  stack.push(cur.left);if(cur.right!=null) stack.push(cur.right); }Collections.reverse(result);return result;}
}

层序遍历

LeetCode 102. 二叉树的层序遍历

题目链接：二叉树的层序遍历题目链接

代码

java">/*** 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 {public List<List<Integer>> levelOrder(TreeNode root) {Queue<TreeNode>queue=new LinkedList<>();List<List<Integer>> result=new ArrayList<List<Integer>>();if(root==null)return result;queue.offer(root);while(!queue.isEmpty()){int size=queue.size();List<Integer> middle=new ArrayList<Integer>();while(size-->0){TreeNode cur=queue.peek();queue.poll();middle.add(cur.val);if(cur.left!=null)  queue.offer(cur.left);if(cur.right!=null) queue.offer(cur.right);}result.add(middle);}return result;}
}