算法练习(12)-二叉树的递归套路

菩提树下的杨过

发布于 2021-11-02 16:19:16

4050

发布于 2021-11-02 16:19:16

如果二叉树的问题,可以分解为先处理左树, 再处理右侧, 这种就可以用"左程云"推荐的所谓"递归套路"解法, 其代码模板大致象下面这样:

class ReturnType{
    //定义要返回的信息
    public ... ;

    //构造函数
    public ReturnType(...){

    }
}

ReturnType process(TreeNode n){
    //退出递归的base条件
    if (n==null){
        ...
    }

    //向左树要信息
    ReturnType leftData = process(n.left);
    //向右树要信息
    ReturnType rightData = process(n.right);

    //...组装最终结果
    return new ReturnType(...);
}

来看几个示例: (注: 以下题目从效率上讲, 可能有更好的解法, 这里只是为了演示如何使用左神的这个递归思路)

示例1: 求二叉树的高度和节点总数?

思路: 整颗树的节点总数 ,等于左子树的节点数+右子树的节点数, 高度=max(左子树的高度, 右子树的高度), 所以这个问题可以分解为不停向左、右子树要高度(height)及节点数(size)

/**
 * 先定义左、右子树需要返回的信息体
 */
static class ReturnType {
    public int height;
    public int size;

    public ReturnType(int h, int size) {
        this.height = h;
        this.size = size;
    }
}

/**
 * 再递归调用
 * @param x
 * @return
 */
static ReturnType process(TreeNode x) {
    //退出递归的边界判断
    if (x == null) {
        return new ReturnType(0, 0);
    }
    //向左树要信息
    ReturnType leftData = process(x.left);
    //向右树要信息
    ReturnType rightData = process(x.right);
    
    //组装左树+右树的信息
    return new ReturnType(Math.max(leftData.height, rightData.height) + 1, leftData.size + rightData.size + 1);
}

示例2：如何判断一颗树是满二叉树?

思路：满二叉树的特性, 最后一层叶子节点都是左右双全的, 而且左＼右子树的高度相等，如果这２个条件满足，必然节点总数＝2^k -1 , 即2的k次方,再减1（注：ｋ为树的高度）

示例１中，已经求出了节点数，以及高度ｋ，只要校验一下ｓｉｚｅ是否等于2^height -1

 /**
     * 先定义左、右子树需要返回的信息体
     */
    static class ReturnType {
        public int height;
        public int size;
        //这个变量，不用左右子树返回，只是放在这里方便最终使用而已
        public boolean isFBT = false;

        public ReturnType(int h, int size) {
            this.height = h;
            this.size = size;
        }
    }

    /**
     * 判断是否满二叉树(Full Binary Tree)
     *
     * @param x
     * @return
     */
    static ReturnType process(TreeNode x) {
        //退出递归的边界判断
        if (x == null) {
            return new ReturnType(0, 0);
        }
        //向左树要信息
        ReturnType leftData = process(x.left);
        //向右树要信息
        ReturnType rightData = process(x.right);

        int height = Math.max(leftData.height, rightData.height) + 1;
        int size = leftData.size + rightData.size + 1;

        //组装左树+右树的信息
        ReturnType returnType = new ReturnType(height, size);
        //检查总节点数符合满2叉树特点
        returnType.isFBT = ((1 << height) - 1) == size;
        return returnType;
    }

示例3：如何判断一颗树是平衡二叉树？

   /**
     * 先定义左、右子树需要返回的信息体
     */
    static class ReturnType {
        public int height;
        //这个变量，不用左右子树返回，只是放在这里方便最终使用而已
        public boolean isAVL = false;

        public ReturnType(int h) {
            this.height = h;
        }
    }

    /**
     * 判断是否满平衡二叉树
     *
     * @param x
     * @return
     */
    static ReturnType process(TreeNode x) {
        //退出递归的边界判断
        if (x == null) {
            return new ReturnType(0);
        }
        //向左树要信息
        ReturnType leftData = process(x.left);
        //向右树要信息
        ReturnType rightData = process(x.right);

        int height = Math.max(leftData.height, rightData.height) + 1;


        //组装左树+右树的信息
        ReturnType returnType = new ReturnType(height);
        returnType.isAVL = Math.abs(leftData.height - rightData.height) <= 1;
        return returnType;
    }

示例4：如何判断一颗树是搜索二叉树？

思路：搜索二叉树的特征, 左边的节点, 肯定比自己小, 右边的节点比自己大. (假设树中没有重复节点) , 违反这个规则就不是搜索二叉树了, 所以可分解为不停向左\右子树询问 "你是不是搜索二叉树? 你的最大节点和最小节点值是多少?"

static class ReturnType {
    public boolean isBst;
    public int min = Integer.MIN_VALUE;
    public int max = Integer.MAX_VALUE;

    public ReturnType(boolean bst, int min, int max) {
        this.isBst = bst;
        this.min = min;
        this.max = max;
    }
}

static ReturnType process(TreeNode n) {
    if (n == null) {
        return null;
    }
    ReturnType leftData = process(n.left);
    ReturnType rightData = process(n.right);
    int min = n.val;
    int max = n.val;
    if (leftData != null) {
        min = Math.min(min, leftData.min);
        max = Math.max(max, leftData.max);
    }
    if (rightData != null) {
        min = Math.min(min, rightData.min);
        max = Math.max(max, rightData.max);
    }
    boolean isBst = true;
    //左树不是搜索树, 或左树的最大节点比自己还大, 整体必然不是搜索二叉树
    if (leftData != null && (!leftData.isBst || leftData.max >= n.val)) {
        isBst = false;
    }
    //右树不是搜索树, 或右树的最小节点比自己还小, 整体必然不是搜索二叉树
    if (rightData != null && (!rightData.isBst || rightData.min <= n.val)) {
        isBst = false;
    }
    return new ReturnType(isBst, min, max);
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2021-10-31 ，如有侵权请联系 cloudcommunity@tencent.com 删除

二叉树