526互联

二叉树（建树|遍历|寻找最大最小深度）

发布时间 2023-03-27 18:51:42作者: 青尤尘

二叉树基础操作

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));
    }
}