首页 > 其他分享 >二叉树(建树|遍历|寻找最大最小深度)

二叉树(建树|遍历|寻找最大最小深度)

时间:2023-03-27 18:56:09浏览次数:36  
标签:遍历 TreeNode System right 二叉树 null root 建树 out

二叉树基础操作

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

相关文章

  • HashMap和LinkedHashMap遍历机制
    原文链接:HashMap和LinkedHashMap遍历机制对HashMap和LinkedHashMap遍历的几种方法以HashMap为例,LinkedHashMap方法一样。一共有三种遍历方式Iterator<Map.Entry......
  • 数据结构与算法基础-----------树与二叉树
                         ......
  • C#遍历指定文件夹中所有文件的3种方法
        前段时间小编同事面试遇到了这个问题,由于同事比较菜并未很完美的完成这个问题,本文就替小编来解答一下。在C#中有多种方式类遍历指定文件夹中的文件,本文将介绍三种......
  • 代码随想录--二叉树
    二叉树二叉树--二叉树的递归遍历题目:144.二叉树的前序遍历(opensnewwindow)145.二叉树的后序遍历(opensnewwindow)94.二叉树的中序遍历题解:前序遍历clas......
  • LeetCode 111.二叉树的最小深度
    1.题目给定一个二叉树,找出其最小深度。最小深度是从根节点到最近叶子节点的最短路径上的节点数量。说明:叶子节点是指没有子节点的节点。示例1:输入:root=[3,9,20,null,null......
  • AcWing 3555. 二叉树
    https://www.acwing.com/problem/content/description/3558/输入样例:18423456-1-1-1-17-1-18-1-1-116464581输出样例:2424详解见代码......
  • 实验2 目录树的遍历
    Unix实验报告实验:实验2目录树的遍历专业:计算机科学与技术班级:1班姓名:姚怀聿学号:229202022046322022年10月21日目录一......
  • 二叉树
    遍历顺序前序:中左右(中在前面就是前序)中序:左中右(中在中间就是中序)后序:左右中(中在前面就是后序)二叉树的非递归遍历https://www.bilibili.com/video/BV15f4y1W7i2前序(非递归)使......
  • 实验2 目录树的遍历
    Unix实验报告实验:实验2目录树的遍历专业:计算机科学与技术班级:1班姓名:姚怀聿学号:229202022046322022年10月21日目录一......
  • LeetCode199.二叉树的右视图
    1.题目:给定一个二叉树的根节点root,想象自己站在它的右侧,按照从顶部到底部的顺序,返回从右侧所能看到的节点值。示例1:输入: [1,2,3,null,5,null,4]输出: [1,3,4]来源:力......