LeetCode ACM模式——二叉树篇（一）-Toy模板网

这篇具有很好参考价值的文章主要介绍了LeetCode ACM模式——二叉树篇（一）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

刷题顺序及思路来源于代码随想录，网站地址：https://programmercarl.com

定义二叉树

创建二叉树

利用前序遍历创建二叉树

利用数组创建二叉树

打印二叉树

144. 二叉树的前序遍历

递归遍历

迭代遍历（利用栈）

145. 二叉树的后序遍历

编辑递归遍历

迭代遍历（利用栈）

94. 二叉树的中序遍历

递归遍历

迭代遍历（利用栈）

定义二叉树

public class TreeNode {
	int val;
	TreeNode left;
	TreeNode right;

	public TreeNode() {
	}

	public TreeNode(int val){
		this.val=val;
	}
	public TreeNode(int val,TreeNode left,TreeNode right){
		this.val=val;
		this.left=left;
		this.right=right;
	}


}

创建二叉树

利用前序遍历创建二叉树

/**
 * @author light
 * @Description 基于前序遍历创建二叉树
 * @create 2023-08-13 20:24
 */
public class BinaryTree {
	TreeNode root; //根节点
	int size;  //树的长度
	int index=0;

    //Integer[] data:数值数组
	public BinaryTree(Integer[] data) {
		this.size=getSize(data);
		root=createTree(data);
	}

	private int getSize(Integer[] data) {
		int size=0;
		for(Integer i:data){
			if(i!=null){
				size++;
			}
		}
		return size;
	}

	public TreeNode createTree(Integer[] data){//递归生成二叉树
		Integer val=data[index++];
		if(val==null){
			return null;
		}
		TreeNode node=new TreeNode(val);
		node.left=createTree(data);
		node.right=createTree(data);
		return node;
	}
}

利用数组创建二叉树

/**
 * @author light
 * @Description 利用数组创建二叉树
 * @create 2023-08-14 12:38
 */
public class BinaryTree2 {
	TreeNode root; //根节点
	int size;  //树的长度
	Integer[] data;

	public BinaryTree2(Integer[] data) {
		this.data=data;
		this.size=getSize(data);
		root=createTree(0);
	}

	private int getSize(Integer[] data) {
		int size=0;
		for(Integer i:data){
			if(i!=null){
				size++;
			}
		}
		return size;
	}
	private TreeNode createTree(int index) {
		if(index>=data.length){
			return null;
		}
		if(data[index]==null){
			return null;
		}
		TreeNode node=new TreeNode(data[index]);
		node.left=createTree(2*index+1);
		node.right=createTree(2*index+2);
		return node;

	}

}

打印二叉树

/**
 * @author light
 * @Description 打印二叉树
 * @create 2023-08-14 13:06
 */
public class BinaryTreePrinter {
	public static void printTree(TreeNode root) {
		printTree(root, 0);
	}

	private static void printTree(TreeNode node, int level) {
		if (node == null) {
			return;
		}
		System.out.print(node.val+"\t");
		printTree(node.left, level + 1);
		printTree(node.right, level + 1);
	}

	public static void main(String[] args) {
		// 创建一个二叉树
		TreeNode root = new TreeNode(1);
		root.left = new TreeNode(2);
		root.right = new TreeNode(3);
		root.left.left = new TreeNode(4);
		root.left.right = new TreeNode(5);
		root.right.left = new TreeNode(6);
		root.right.right = new TreeNode(7);

		// 打印二叉树
		printTree(root);
	}

}

144. 二叉树的前序遍历

给你二叉树的根节点 root ，返回它节点值的前序遍历。

LeetCode ACM模式——二叉树篇（一）,做题总结,leetcode,算法,BinaryTree,java

递归遍历



import java.util.ArrayList;
import java.util.List;

/**
 * @author light
 * @Description 二叉树的前序遍历
 * @create 2023-08-13 19:43
 */
public class PreorderTraversalTest {
	public static void main(String[] args) {
		Integer[] data={1, 2, 4, null, null, 5, null, null, 3, null, null };

		BinaryTree tree=new BinaryTree(data);
		System.out.println("递归前序遍历：");
		List<Integer> res1=preorderTraversal_Recursion(tree.root);
		System.out.println(res1);

	}

	//递归遍历
	public static List<Integer> preorderTraversal_Recursion(TreeNode root) {
		List<Integer> res=new ArrayList<>();
		traversal(root,res);
		return res;
	}
	public static void traversal(TreeNode root,List<Integer> res){
		if(root==null){
			return ;
		}
		res.add(root.val); //中
		traversal(root.left,res); //左
		traversal(root.right,res); //右

	}
	
}

迭代遍历（利用栈）


import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * @author light
 * @Description 二叉树的前序遍历
 * @create 2023-08-13 19:43
 */
public class PreorderTraversalTest {
	public static void main(String[] args) {
		Integer[] data={1, 2, 4, null, null, 5, null, null, 3, null, null };

		BinaryTree tree=new BinaryTree(data);
		System.out.println("迭代前序遍历");
		List<Integer> res2=preorderTraversal_Iterate(tree.root);
		System.out.println(res2);

	}

	//迭代遍历(利用栈:前序遍历顺序：中-左-右，入栈顺序：中-右-左
	public static List<Integer> preorderTraversal_Iterate(TreeNode root) {
		List<Integer> list=new ArrayList<>();
		Deque<TreeNode> stack=new ArrayDeque<>();
		if(root==null){
			return list;
		}
		stack.push(root);
		while(!stack.isEmpty()){
			TreeNode node=stack.pop();
			list.add(node.val);
			if(node.right!=null){
				stack.push(node.right);
			}
			if(node.left!=null){
				stack.push(node.left);
			}
		}
		return list;
	}
}

145. 二叉树的后序遍历

给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。

递归遍历

import java.util.ArrayList;
import java.util.List;

/**
 * @author light
 * @Description 二叉树后序遍历
 * @create 2023-08-13 19:46
 */
public class PostorderTraversalTest {
	public static void main(String[] args) {
		Integer[] data={1, 2, 4, null, null, 5, null, null, 3, null, null };
		BinaryTree tree=new BinaryTree(data);

		System.out.println("递归后序遍历：");
		List<Integer> res1=postorderTraversal_Recursion(tree.root);
		System.out.println(res1);

	}

	//递归遍历
	public static List<Integer> postorderTraversal_Recursion(TreeNode root) {
		List<Integer> res=new ArrayList<>();
		traversal_Recursion(root,res);
		return res;
	}

	public static void traversal_Recursion(TreeNode root,List<Integer> res){
		if(root==null){
			return;
		}
		traversal_Recursion(root.left,res);//左
		traversal_Recursion(root.right,res);//右
		res.add(root.val);//中
	}
	
}

迭代遍历（利用栈）

import java.util.*;

/**
 * @author light
 * @Description 二叉树后序遍历
 * @create 2023-08-13 19:46
 */
public class PostorderTraversalTest {
	public static void main(String[] args) {
		Integer[] data={1, 2, 4, null, null, 5, null, null, 3, null, null };
		BinaryTree tree=new BinaryTree(data);

		System.out.println("迭代后续遍历");
		List<Integer> res2=postorderTraversal_Iterate(tree.root);
		System.out.println(res2);

	}
	//迭代遍历(利用栈:后序遍历顺序：左-右-中，入栈顺序：中-左-右 出栈顺序：中-右-左， 最后翻转结果
	public static List<Integer> postorderTraversal_Iterate(TreeNode root) {
		List<Integer> list=new ArrayList<>();
		Deque<TreeNode> stack=new ArrayDeque<>();
		if(root==null){
			return list;
		}
		stack.push(root);
		while(!stack.isEmpty()){
			TreeNode node=stack.pop();
			list.add(node.val);
			if(node.left!=null){
				stack.push(node.left);
			}
			if(node.right!=null){
				stack.push(node.right);
			}
		}
		Collections.reverse(list);
		return list;
	}
}

94. 二叉树的中序遍历

给定一个二叉树的根节点 root ，返回 它的中序遍历 。文章来源地址https://www.toymoban.com/news/detail-651198.html

递归遍历

import java.util.ArrayList;
import java.util.List;

/**
 * @author light
 * @Description 二叉树中序遍历
 * @create 2023-08-13 19:48
 */
public class InorderTraversalTest {
	public static void main(String[] args) {
		Integer[] data={1, 2, 4, null, null, 5, null, null, 3, null, null };
		BinaryTree tree=new BinaryTree(data);
		System.out.println("递归中序遍历");
		List<Integer> res=inorderTraversal_Recursion(tree.root);
		System.out.println(res);
	}

	//递归遍历
	public static List<Integer> inorderTraversal_Recursion(TreeNode root) {
		List<Integer> res=new ArrayList<>();
		traversal_Recursion(root,res);
		return res;
	}

	public static void traversal_Recursion(TreeNode root,List<Integer> res){
		if(root==null){
			return;
		}
		traversal_Recursion(root.left,res);//左
		res.add(root.val);//中
		traversal_Recursion(root.right,res); //右

	}
	
}

迭代遍历（利用栈）



import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * @author light
 * @Description 二叉树中序遍历
 * @create 2023-08-13 19:48
 */
public class InorderTraversalTest {
	public static void main(String[] args) {
		Integer[] data={1, 2, 4, null, null, 5, null, null, 3, null, null };
		BinaryTree tree=new BinaryTree(data);
		System.out.println("迭代中序遍历");
		List<Integer> res2=inorderTraversal_Iterate(tree.root);
		System.out.println(res2);
	}

	//迭代遍历
	public static List<Integer> inorderTraversal_Iterate(TreeNode root) {
		List<Integer> list=new ArrayList<>();
		TreeNode cur=root;//用来遍历二叉树
		Deque<TreeNode> stack=new ArrayDeque<>(); //用来存放遍历过的结点
		if(cur==null){
			return list;
		}
		while(cur!=null||!stack.isEmpty()){
			if(cur!=null){
				stack.push(cur);
				cur=cur.left;
			}else {
				cur=stack.pop();
				list.add(cur.val);
				cur=cur.right;
			}
		}
		return list;
	}
}

到了这里，关于LeetCode ACM模式——二叉树篇（一）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！