二叉树的遍历总结
前序：https://leetcode.cn/problems/binary-tree-preorder-traversal/
中序：https://leetcode.cn/problems/binary-tree-inorder-traversal/
后序：https://leetcode.cn/problems/binary-tree-postorder-traversal/
层次：https://leetcode.cn/problems/binary-tree-level-order-traversal/
二叉树的递归遍历
//递归写法
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
add(root,res);
return res;
}
//前序遍历
public void add(TreeNode root,List<Integer> res){
if(root==null) return ;
res.add(root.val);//根
add(root.left,res);//左
add(root.right,res);//右
}
//中序遍历
public void add(TreeNode root,List<Integer> res){
if(root==null) return ;
add(root.left,res);//左
res.add(root.val);//根
add(root.right,res);//右
}
//后序遍历
public void add(TreeNode root,List<Integer> res){
if(root==null) return ;
add(root.left,res);//左
add(root.right,res);//右
res.add(root.val); //根
}
}
二叉树的迭代遍历
//前序遍历 右左入 左右出
class Solution {
//迭代写法
public List<Integer> preorderTraversal(TreeNode root) {
Stack<TreeNode> stack = new Stack<TreeNode>();
List<Integer> res = new ArrayList<>();
while(root!=null){
res.add(root.val);//根
if(root.right!=null)stack.push(root.right);//右
if(root.left!=null)stack.push(root.left);//左
root=stack.isEmpty()?null:stack.pop();
}
return res;
}
}
//中序遍历
class Solution {
List<Integer> list = new ArrayList<>();
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
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 {
public List<Integer> postorderTraversal(TreeNode root) {
Stack<TreeNode> stack = new Stack<TreeNode>();
List<Integer> res = new ArrayList<>();
while(root!=null){
res.add(root.val);
if(root.left!=null)stack.push(root.left);
if(root.right!=null)stack.push(root.right);
root=stack.isEmpty()?null:stack.pop();
}
Collections.reverse(res);
return res;
}
}
//前中后的统一迭代遍历
//使用空标记下一节点为可添加节点
//前序遍历
class Solution {
//迭代写法
public List<Integer> preorderTraversal(TreeNode root) {
Stack<TreeNode> stack = new Stack<TreeNode>();
List<Integer> res = new ArrayList<>();
if(root==null) return res;
stack.push(root);
while(!stack.isEmpty()){
root = stack.pop();
if(root!=null){
if(root.right!=null)stack.push(root.right);//右
if(root.left!=null)stack.push(root.left); //左
stack.push(root);//根
stack.push(null);//标记下一节点
}else{
//处理标记节点
root = stack.pop();
res.add(root.val);
}
}
return res;
}
}
//中序遍历
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
Stack<TreeNode> stack = new Stack<TreeNode>();
List<Integer> res = new ArrayList<>();
if(root==null) return res;
stack.push(root);
while(!stack.isEmpty()){
root = stack.pop();
if(root!=null){
if(root.right!=null)stack.push(root.right);
stack.push(root);
stack.push(null);
if(root.left!=null)stack.push(root.left);
}else{
root = stack.pop();
res.add(root.val);
}
}
return res;
}
}
//后序遍历
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
Stack<TreeNode> stack = new Stack<TreeNode>();
List<Integer> res = new ArrayList<>();
if(root==null) return res;
stack.push(root);
while(!stack.isEmpty()){
root = stack.pop();
if(root!=null){
stack.push(root);
stack.push(null);
if(root.right!=null)stack.push(root.right);
if(root.left!=null)stack.push(root.left);
}else{
root = stack.pop();
res.add(root.val);
}
}
return res;
}
}
层次遍历
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
Queue<TreeNode> q = new LinkedList<>();
if(root == null) return res;
q.offer(root);
while(!q.isEmpty()){
int size = q.size();
List<Integer> list = new ArrayList<>();
for(int i =0;i<size;i++){
TreeNode t = q.poll();
list.add(t.val);
if(t.left!=null) q.offer(t.left);
if(t.right!=null) q.offer(t.right);
}
res.add(list);
}
return res;
}
}
建二叉树
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;
}
}
public class CreateTree {
public static void main(String[] args) {
TreeNode root = create();//建树
show(root);//前序遍历树
}
private static void show(TreeNode root){
if (root == null) return;
System.out.print(root.val+" ");
show(root.left);
show(root.right);
}
//类似于层次遍历
private static TreeNode create() {
Scanner scanner = new Scanner(System.in);
String str = scanner.nextLine();
String substring = str.substring(1, str.length()-1);
String[] strs = substring.split(",");//获取输入的字符串序列
if (strs.length == 0) return null;
Queue<TreeNode> queue = new LinkedList<>();
TreeNode root = new TreeNode(Integer.parseInt(strs[0]));
queue.offer(root);
int i=1;//记录序列遍历数量
while (i<strs.length){
int size = queue.size();//记录当前层次的节点数量
for (int j = 0;j<size;j++){
TreeNode t = queue.poll();
if (!strs[i].equals("null")){
t.left = new TreeNode(Integer.parseInt(strs[i]));
queue.offer(t.left);//非空子树入队
}
i++;
if (!strs[i].equals("null")){
t.right = new TreeNode(Integer.parseInt(strs[i]));
queue.offer(t.right);
}
i++;
}
}
return root;
}
}