二叉树基础操作
1.实现思路
建树:递归从数组中按照层级建立
递归:提供6种建树操作(前、中、后序递归和非递归)
最大深度:利用回溯|递归实现两种操作
最小深度:利用递归实现
2.代码实现
import java.util.Deque;
import java.util.LinkedList;
import java.util.Stack;
class TreeNode {
TreeNode left;
TreeNode right;
int val;
TreeNode(int val) {
this.val = val;
}
// 层级顺序 i=-1表示
static TreeNode createTree(int[] vals, int i) {
if (i >= vals.length || vals[i] == -1)
return null;
TreeNode a = new TreeNode(vals[i]);
a.left = createTree(vals, 2 * i + 1);
a.right = createTree(vals, 2 * i + 2);
return a;
}
// 层级遍历 队列实现
static void BFS(TreeNode root) {
if (root == null)
return;
Deque<TreeNode> q = new LinkedList<>();
q.offer(root);
while (!q.isEmpty()) {
int s = q.size();
for (int i = 0; i < s; i++) {
TreeNode t = q.poll();
// operate
System.out.print(t.val + " ");
if (t.left != null) {
q.offer(t.left);
}
if (t.right != null) {
q.offer(t.right);
}
}
System.out.println();
}
}
// 先序遍历 递归实现
static void preorderTraseval(TreeNode root) {
if (root != null)
System.out.print(root.val + " ");
else
return;
preorderTraseval(root.left);
preorderTraseval(root.right);
}
// 中序遍历 递归实现
static void inorderTraseval(TreeNode root) {
if (root == null)
return;
inorderTraseval(root.left);
System.out.print(root.val + " ");
inorderTraseval(root.right);
}
// 后序遍历 递归实现
static void postorderTraseval(TreeNode root) {
if (root == null)
return;
postorderTraseval(root.left);
postorderTraseval(root.right);
System.out.print(root.val + " ");
}
// 先序遍历 迭代遍历 中 左 右
static void preorderTraseval2(TreeNode root) {
Stack<TreeNode> s = new Stack<>();
if (root == null)
return;
s.push(root);
while (!s.isEmpty()) {
TreeNode t = s.pop();
System.out.print(t.val + " ");
if (t.right != null)
s.push(t.right);
if (t.left != null)
s.push(t.left);
}
}
// 中序遍历 迭代遍历
static void inorderTraseval2(TreeNode root) {
Stack<TreeNode> s = new Stack<>();
if (root == null)
return;
while (root != null || !s.isEmpty()) {
if (root != null) {
s.push(root);
root = root.left;
} else {
root = s.pop();
System.out.print(root.val + " ");
root = root.right;
}
}
}
// 后序遍历 迭代遍历 中 左 右
// 后 左 右 中 中 右 左 反过来
static void postorderTraseval2(TreeNode root) {
Stack<TreeNode> s = new Stack<>();
Stack<Integer> res = new Stack<>();
if (root == null)
return;
s.push(root);
while (!s.isEmpty()) {
TreeNode t = s.pop();
res.push(t.val);
if (t.left != null)
s.push(t.left);
if (t.right != null)
s.push(t.right);
}
while(!res.isEmpty()){
System.out.print(res.pop()+" ");
}
}
//递归求二叉树最大深度
static int findmaxDepth(TreeNode root){
if(root == null)return 0;
int l = findmaxDepth(root.left)+1;
int r = findmaxDepth(root.right)+1;
return Math.max(l, r);
}
static int depth2 = 0;
//前序求二叉树最大深度 回溯
static void findmaxDepth2(TreeNode root,int depth){
depth2 = Math.max(depth2, depth);
if(root.left==null&&root.right==null)return;
if(root.left!=null){
depth++;
findmaxDepth2(root.left, depth);
depth--;
}
if(root.right!=null){
depth++;
findmaxDepth2(root.right, depth);
depth--;
}
return;
}
//求二叉树最小深度
static int findminDepth(TreeNode root){
if(root==null)return 0;
// 当一个左子树为空,右不为空,这时并不是最低点
int left = findminDepth(root.left);
int right = findminDepth(root.right);
if(root.left==null&&root.right!=null){
return 1+right;
}
if(root.left!=null&&root.right==null){
return 1+left;
}
return 1 + Math.min(right, left);
}
}
public class Main {
public static void main(String[] args) {
int aa[] = { 1, 2, 3, 4, 5,6,7 };
// 先序 1 2 4 5 3 6 7
// 中序 4 2 5 1 6 3 7
// 后序 4 5 2 6 7 3 1
TreeNode root = TreeNode.createTree(aa, 0);
System.out.println(root.val);
TreeNode.BFS(root);
System.out.println("preorderTravesal:");
TreeNode.preorderTraseval(root);
System.out.println();
TreeNode.preorderTraseval2(root);
System.out.println();
System.out.println("inoderTravesal:");
TreeNode.inorderTraseval(root);
System.out.println();
TreeNode.inorderTraseval2(root);
System.out.println();
System.out.println("postorderTravesal:");
TreeNode.postorderTraseval(root);
System.out.println();
TreeNode.postorderTraseval2(root);
System.out.println();
System.out.println("MaxDepth:");
System.out.println(TreeNode.findmaxDepth(root));
TreeNode.findmaxDepth2(root, 1);
System.out.println(TreeNode.depth2);
System.out.println("MinDepth:");
System.out.println(TreeNode.findminDepth(root));
}
}
标签:遍历,TreeNode,System,right,二叉树,null,root,建树,out
From: https://www.cnblogs.com/bjtu-QYC/p/17262523.html