二叉树的千层套路之递归 (树形dp)

拿到一个题目,先假设以任意一个节点作为头部的条件下,答案要怎么求。
假设可以向左右子树要条件的情况下,怎么列出答案的可能性。

判断一颗二叉树是否是搜索二叉树

搜索二叉树:对每一个子树,左子树的值都小于根,右子树的值都大于根

实现:

  1. 中序遍历。判断中序遍历是否是升序排列即可

    中序遍历的值就是左中右

  2. 上述的二叉树递归套路

    以节点x为节点,他是二叉搜索树的条件:

    1. 左树是二叉搜索树
    2. 右子树是二叉搜索树
    3. 左子树上的最大值 < x
    4. 右子树上的最小值 > x

    上述条件成立则该树是二叉搜索树

    对左右子树,需要的条件是:

    左子树:是不是二叉搜索树 , 左子树的最大值
    右子树:是不是二叉搜索树 , 右子树的最小值

    因为是递归函数,所以每个节点都是一样的,对此问题,一定要返回三个信息

    1. 整棵树是不是二叉搜索树
    2. 整棵树的最大值是多少
    3. 整棵树的最小值是多少
static class Info{
        public boolean isBST;
        public int max;
        public int min;

        public Info(boolean isBST, int max, int min) {
            this.isBST = isBST;
            this.max = max;
            this.min = min;
        }
    }
public static Info isBST_2(TreeNode x){
        if (x == null) return null;
        Info leftData = isBST_2(x.left);//左树可以返回他要的信息
        Info rightData = isBST_2(x.right);//右子树可以返回他要的信息

        //整棵树,在不考虑子树的情况下 , 最小最大就是自己的值
        int min = x.val;
        int max = x.val;

        //左子树如果有信息 , 更新信息
        if (leftData != null){
            min = Math.min(min , leftData.min);
            max = Math.max(min , leftData.max);
        }
        //右子树如果有信息 , 更新信息
        if (rightData != null){
            min = Math.min(min , rightData.min);
            max = Math.max(max , rightData.max);
        }

        //先认为整棵树不是搜索二叉树
        boolean isBST = false;
        //条件成立的情况下 , 才是二叉搜索树

        if (
                //左树不为空 , 检查左子树是不是二叉搜索树 且 左子树的最大值小于我x的值
                //左子树为空 , 则不影响不考虑 ,就为true
                (leftData != null ? (leftData.isBST && leftData.max < x.val) : true)
                &&
                (rightData != null ? (rightData.isBST && rightData.min > x.val) : true)
                //右子树不为空 , 检查右子树是不是二叉搜索树 且 右子树的最小值大于我x的值
                //右子树为空 , 则不影响不考虑 ,就为true
        ){
            //如果上述都成立  ,则以x为根的节点就是二叉搜索树
            isBST = true;
        }

        return new Info(isBST , max , min);
    }
    public static boolean isBST(TreeNode root){
        Info bst = isBST_2(root);
        return bst.isBST;
    }

判断一颗二叉树是否是满二叉树

满二叉树: 如果一个最大深度是h , 节点数如果是n , 则只有满二叉树满足 N = 2 ^ h - 1 .

实现:

  1. 利用N = 2 ^ h - 1 , 统计节点值 , 和最大深度 , 判断是否满足表达式

  2. 递归套路

    1. 信息体 : 以 x 为根节点的树是否是满二叉树需要的条件(信息)
      1. 以x为根节点最大深度
      2. 以x为根节点的节点数

    对于N = 2 ^ h - 1的判断,我们放到上一层非递归函数里计算即可

static class Info{
        int MaxH;
        int Nodes;
        public Info(int maxH, int nodes) {
            MaxH = maxH;
            Nodes = nodes;
        }
    }

    public static boolean isCBT(TreeNode root){
        Info info = process(root);
        int maxH = info.MaxH;
        int nodes = info.Nodes;

        return nodes == (1 << maxH) - 1;
    }
    public static Info process(TreeNode x){
        //空 , 最大深度和节点数都是0
        if (x == null)
            return new Info(0,0);

        //得到左子树的信息
        Info leftData = process(x.left);
        //得到右子树的信息
        Info rightData = process(x.right);

        //以x为根的高度和节点数
        int maxH = leftData.MaxH + rightData.MaxH + 1;
        int nodes = leftData.Nodes + rightData.Nodes  + 1;

        return new Info(maxH,nodes);
    }

判断以可二叉树是否是平衡二叉树

平衡二叉树:每一颗子树 , 左子树与右子树的高度差不超过一

对于此问题 , 需要的信息:

  1. 左子树的高度
  2. 右子树的高度
  3. 左子树是不是平衡二叉树
  4. 右子树是不是平衡二叉树

归纳一下 , 我们需要返回的信息体:

  1. 高度
  2. 是不是二叉搜索树

以x为根节点的树是平衡二叉树的条件是:

左子树是平衡二叉树 && 右子树是平衡二叉树 && | 以x为根节点的左子树的高 - 以x为根节点的右子树子树的高 | <= 1

实现

static class Info{
        int heigh ;
        boolean isBT;

        public Info(int heigh, boolean isBT) {
            this.heigh = heigh;
            this.isBT = isBT;
        }
    }


    public static boolean isBT(TreeNode root){
        Info process = process(root);
        return process.isBT;
    }
    public static Info process(TreeNode x){
        if (x == null)
            return new Info(0 , true);

        Info leftData = process(x.left);
        Info rightData = process(x.right);

        int heigh = (leftData.heigh > rightData.heigh ? leftData.heigh : rightData.heigh) + 1;
        boolean isBT = leftData.isBT && rightData.isBT && Math.abs(leftData.heigh - rightData.heigh) < 2 ? true : false;

        return new Info(heigh , isBT);
    }

给定两个二叉树的节点Node1 和 Node2 求最低公共祖先

公共祖先的定义 : 不解释

分析

以x为根节点的子树 , 对node1 和node2节点

  1. 既没有node1 也没有 node2 节点 , 说明在x树下 没有最低公共祖先
  2. 如果node1 和 node2 只有一个节点在x树下 ,最低公共祖先不在x子树内 , 但是可以记录下发现的节点
  3. 如果两个节点都在这个树上
    1. 如果左树含有一个 , 右树含有一个 , 那最低公共祖先就是x
    2. 如果都在左树或者右树 , 那么得到的最低公共祖先就是x树下的答案
    3. 如果左子树或者右子树里只发现一个 , 且 x 等于另外一个 , 那么x 就是最低公共祖先
    4. 如果都不在左右子树 , 或者只有一个在左子树或右子树 且 x不等于另外一个 , 那么不存在最低公共祖先
    5. 如果其中一个为空 , 那么不存在

最终需要返回的信息

  1. 是否已经发现了node1 和 node2 最低公共祖先
  2. 整棵树上是否发现了节点node1
  3. 整棵树上是否发现了节点node2

代码实现

static class Info{
        boolean findNode1;
        boolean findNode2;
        TreeNode findLowCA;

        public Info(boolean findNode1, boolean findNode2, TreeNode lowCA) {
            this.findNode1 = findNode1;
            this.findNode2 = findNode2;
            this.findLowCA = lowCA;
        }
    }

    public static TreeNode findLowCA(TreeNode root , TreeNode node1 , TreeNode node2){
        Info info = process(root, node1, node2);
        return info.findLowCA;
    }
    public static Info process(TreeNode x , TreeNode node1 , TreeNode node2){
        if (x == null)
            return new Info(false,false,null);

        Info leftData = process(x.left , node1 , node2);
        Info rightData = process(x.right , node1 , node2);

        //左右发现一个就返回
        if (leftData.findLowCA != null){
            return new Info(true,true,leftData.findLowCA);
        }
        if (rightData.findLowCA != null){
            return new Info(true,true,rightData.findLowCA);
        }

        //左右两树都没有发现最低公共祖先

        //如果左树发现了1 且 右树发现了2
        if (leftData.findNode1 && rightData.findNode2){
            return new Info(true,true,x);
        }
        //如果右子树发现了1 且 左子树发现了2
        if (leftData.findNode2 && rightData.findNode1){
            return new Info(true,true,x);
        }

        //如果左右子树都没有发现最低公共祖先 , 且最低公共祖先不是x ,
        // 那么 说明  只有一个节点或者一个节点都不在x的子树上


        //下面的情况都是 只有一个节点在x的子树上 且 x是其中一个节点

        //上面都没有看节点x是不是节点1 或者 节点2
        boolean findNode1 = x == node1;
        boolean findNode2 = x == node2;

        //如果左树发现了node1 或者 右子树发现了node1——只发现了node1
        if (leftData.findNode1 || rightData.findNode1){
            //如果x是node2 , 最低公共祖先就是x
            if (findNode2)
                return new Info(true,true,x);
            //x不是node2 , 没发现node2 , 也没发现公共祖先
            else
                return new Info(true,false,null);
        }

        if (leftData.findNode2 || rightData.findNode2) {
            if (findNode1)
                return new Info(true, true, x);
            else
                return new Info(false, true, null);
        }

        //左右子树都没有发现 , 一个节点都不在x树上
        return new Info(findNode1, findNode2,null);

    }



//主函数测试
    public static void main(String[] args) {
        TreeNode root = new TreeNode(0);
        root.left = new TreeNode(1);
        root.right = new TreeNode(2);

        root.left.left = new TreeNode(3);
        root.left.right = new TreeNode(4);

        root.right.left = new TreeNode(5);
        root.right.right = new TreeNode(6);

        //正确情况应该输出1;
        System.out.println(findLowCA(root, root.left.left, root.left.right) == null ? "NULL" :findLowCA(root, root.left.left, root.left.right).val);

        //正确应该输出NULL
        System.out.println(findLowCA(root,root.left,new TreeNode(666)) == null ? "NULL" : findLowCA(root,root.left,new TreeNode(666)).val);

        //正确应该输出0
        System.out.println(findLowCA(root, root.left.left, root.right.right) == null ? "NULL" : findLowCA(root, root.left.left, root.right.right).val);

        //正确应该输出0
        System.out.println(findLowCA(root, root, root.left) == null ? "NULL" : findLowCA(root, root, root.left).val);

        //正确输出应该为null
        System.out.println(findLowCA(root, root.left.left, null) == null ? "NULL" : findLowCA(root, root.left.left, null).val);
    }

判断一棵树是否是完全二叉树

完全二叉树是一种特殊的二叉树,满足以下要求:

  1. 所有叶子节点都出现在 k 或者 k-1 层,而且从 1 到 k-1 层必须达到最大节点数;

  2. 第 k 层可以不是满的,但是第 k 层的所有节点必须集中在最左边。 需要注意的是不要把完全二叉树和“满二叉树”搞混了,完全二叉树不要求所有树都有左右子树,但它要求:

  3. 任何一个节点不能只有左子树没有右子树

  4. 叶子节点出现在最后一层或者倒数第二层,不能再往上

举例

        o                   o                    o
       / \                 / \                  / \
      o   o               o   o                o   o
     / \  /              /    /\              /   / \
                                             o   o   o
                                            / \ / \ / \
    是完全二叉树          不是完全二叉树        不是完全二叉树

通过观察 , 发现 , 完全二叉树的特点和宽度优先遍历有些相似 , 都是从左到右判断。
因此 , 容易想到 ,可以通过一个宽度优先遍历来进行改造判断
只不过对每个节点需要满足以下条件:

  1. 不能有 右孩子且没有左孩子
  2. 满足1的条件下 , 如果遇到孩子不双全的节点 , 接下来遇到的节点必须是叶节点

代码实现

public static boolean isCBT(TreeNode root){
        if (root == null)
            return true;

        LinkedList<TreeNode> queue = new LinkedList<>();

        //是否遇到过两个孩子不双全的节点
        boolean isMeetNoChild = false;

        //记录左右孩子
        TreeNode left = null;
        TreeNode right = null;

        queue.add(root);
        while (!queue.isEmpty()){

            root = queue.poll();
            left = root.left;
            right = root.right;

            if (
                    //遇见过不双全的孩子 , 且当前节点不是叶子节点
                    (isMeetNoChild && !(left == null && right == null))
                    ||
                    //当前节点的左孩子是空的 , 但是右孩子不为空
                    (left == null && right != null)
            ){
                return false;
            }

            if (root.left != null) {
                queue.add(root.left);
            }
            if (root.right != null) {
                queue.add(root.right);
            }

            //遇见不双全的节点了
            if (left == null || right == null){
                isMeetNoChild = true;
            }
        }

        return true;
    }
  • 微信
  • 快加我微信吧~
  • QQ
  • 快加我QQ吧~
  • weinxin
Betterts

发表评论 取消回复