乐趣区

关于算法:二叉树递归套路2判断二叉树是否是搜索二叉树二叉树的最大距离

本篇持续来聊聊二叉树的递归套路。

一、判断二叉树是否是搜寻二叉树

搜寻二叉树定义:二叉树中的任意一个以 X 为头的子树,左子树都比 X 小,右子树都比 X 大。(经典的搜寻二叉树是没有反复值的)

1、经典做法

中序遍历,后果是递增的,阐明这是搜寻二叉树。

2、递归套路思路

剖析任意一个以 X 为头的子树,满足以 X 为头的子树是搜寻二叉树的条件(列出所有可能性

1)左子树是搜寻二叉树

2)右子树是搜寻二叉树

3)左子树的最大值 小于 X

4)右子树的最小值 大于 X

满足这四个条件能力说以 X 为头的子树是均衡二叉树。

问题来了:此时发现我须要从左子树和右子树中获取的后果不统一(一个是要最小值、一个是要最大值),不好拼凑出递归。咋办?好说,咱们间接求选集(小孩子才做抉择,成年人不做抉择,都要),左子树咱们求最大值和最小值,右子树也是。

也就是每次从左子树和右子树中咱们都须要 是否搜寻二叉树、最大值、最小值 三个数据,只管咱们最初只返回是否搜寻二叉树,然而咱们须要最大值和最小值来辅助咱们判断是否搜寻,所以能够定义如下的 Info 类

/**
 * @author Java 和算法学习:周一
 */
public static class Info {
    public boolean isSearch;
    public int max;
    public int min;

    public Info(boolean isSearch, int max, int min) {
        this.isSearch = isSearch;
        this.max = max;
        this.min = min;
    }
}

3、递归套路代码

(1)首先判断为空时好不好设置,此时不好设置,节点为空时 max 和 min 不好指定,所以节点为空时间接返回 null,前面递归时再解决这个 null 即可。

(2)而后依据列出的所有可能性,编写递归套路的代码,因为要整个造成递归,所以每一步都要返回 Info 类。(无脑拿到左右子树的 Info、拼凑本人的 Info、返回本人的 Info)

/**
 * 判断是否是搜寻二叉树的递归套路写法
 *
 * @author Java 和算法学习:周一
 */
public static Info process(Node x) {
    // 为空时,max 和 min 无奈赋值,所以此处返回 null
    if (x == null) {return null;}

    // 获取左右子树的数据
    Info leftInfo = process(x.left);
    Info rightInfo = process(x.right);

    // 拼凑本人的数据
    boolean isSearch = true;
    // 以后节点不是搜寻二叉树的状况
    // 1. 左子树不是搜寻二叉树
    // 2. 右子树不是搜寻二叉树
    // 3. 左子树最大值大于以后节点
    // 4. 右子树最小值小于以后节点
    if (leftInfo != null && (!leftInfo.isSearch || leftInfo.max >= x.value)) {isSearch = false;}
    if (rightInfo != null && (!rightInfo.isSearch || rightInfo.min <= x.value)) {isSearch = false;}

    int max = x.value;
    int min = x.value;
    if (leftInfo != null) {max = Math.max(leftInfo.max, max);
        min = Math.min(leftInfo.min, min);
    }
    if (rightInfo != null) {max = Math.max(rightInfo.max, max);
        min = Math.min(rightInfo.min, min);
    }

    return new Info(isSearch, max, min);
}

(3)主函数调用递归办法获取后果

/**
 * @author Java 和算法学习:周一
 */
public static boolean isSearchBinaryTree(Node head) {if (head == null) {return true;}
    return process(head).isSearch;
}

所有代码地址:

https://github.com/monday-pro…

二、二叉树的最大间隔

给定一个二叉树,任何两个节点之间都存在间隔,返回整个二叉树的最大间隔。两个节点的间隔示意从一个节点到另一个节点最短门路上的节点数(蕴含两个节点本人)

1、递归套路思路

首先剖析以 X 为头的二叉树,它的最大间隔的可能性有两类,不通过 X、通过 X。

不通过 X:须要获取左子树和右子树各自的最大间隔

通过 X:(左树高度 + 右树高度 + 1)即是最大间隔

也就是每次从左子树和右子树中咱们都须要 最大间隔、高度 两个数据,最初再取 左子树最大间隔、右子树最大间隔、(左树高度 + 右树高度 + 1)的最大值 即是整个树的最大间隔。只管咱们最初只返回最大间隔,然而咱们须要高度来辅助咱们计算最大间隔,所以能够定义如下的 Info 类

/**
 * @author Java 和算法学习:周一
 */
public static class Info {
    public int height;
    public int maxDistance;

    public Info(int height, int maxDistance) {
        this.height = height;
        this.maxDistance = maxDistance;
    }
}

2、递归套路代码

(1)首先判断为空时好不好设置,此时是好设置的,节点为空时 new Info(0, 0),即认为空节点高度为 0、最大间隔为 0。

(2)而后依据列出的所有可能性,编写递归套路的代码,因为要整个造成递归,所以每一步都要返回 Info 类。(无脑拿到左右子树的 Info、拼凑本人的 Info、返回本人的 Info

/**
 * 求二叉树的最大间隔的递归套路写法
 * 
 * @author Java 和算法学习:周一
 */
public static Info process(Node x) {if (x == null) {return new Info(0, 0);
    }

    // 获取左右子树的信息
    Info leftInfo = process(x.left);
    Info rightInfo = process(x.right);

    // 拼凑解决本人的信息
    // 最大高度是 左右子树最大高度 + 1
    int height = Math.max(leftInfo.height, rightInfo.height) + 1;
    // 最大间隔是 左子树最大间隔、右子树最大间隔、(左树高度 + 右树高度 + 1)三个的最大值
    int maxDistance = Math.max((leftInfo.height + rightInfo.height + 1),
            Math.max(leftInfo.maxDistance, rightInfo.maxDistance));

    return new Info(height, maxDistance);
}

(3)主函数调用递归办法获取后果

/**
 * @author Java 和算法学习:周一
 */
public static int maxDistance(Node head) {if (head == null) {return 0;}
    return process(head).maxDistance;
}

所有代码地址:

https://github.com/monday-pro…

这是二叉树递归套路解法的第二篇,联合上一篇是不是发现又有了新的播种呢。这次咱们又学会了左右子树须要获取的值不同时如何解决、在节点为空时不好设置值时如何解决等

退出移动版