求二叉树中最大的二叉搜索子树的头节点

作者：Grey

原文地址：

博客园：求二叉树中最大的二叉搜索子树的头节点

CSDN：求二叉树中最大的二叉搜索子树的头节点

题目描述

给定一棵二叉树的头节点head， 返回这颗二叉树中最大的二叉搜索子树的头节点。

暴力解法

定义递归函数

TreeNode maxSubBSTHead1(TreeNode head)

递归含义表示：以head为头的二叉树中最大的二叉搜索子树的头结点是什么。

接下来是 base case，

    if (head == null) {
      return null;
    }

定义一个辅助函数getBSTSize(head)，这个函数表示：如果以head为头的树是二叉搜索树，则返回其大小，否则返回 0。

getBSTSize(head)的实现思路也比较简单，即通过中序遍历收集以 head 为头的树，如果这个树满足二叉搜索子树，则返回二叉搜索子树的大小，如果以 head 的头不是二叉搜索树，直接返回 0。

代码如下

  public static int getBSTSize(TreeNode head) {
    if (head == null) {
      return 0;
    }
    ArrayList<TreeNode> arr = new ArrayList<>();
    // 中序遍历收集以 head 为头的二叉树，存在数组中
    in(head, arr);
    for (int i = 1; i < arr.size(); i++) {
      if (arr.get(i).val <= arr.get(i - 1).val) {
        return 0;
      }
    }
    return arr.size();
  }

实现了如上方法，主函数直接做如下调用即可，代码说明见注释：

  
  public static TreeNode maxSubBSTHead1(TreeNode head) {
    if (head == null) {
      return null;
    }
    // 以 head 为头的二叉搜索子树大小不为0，说明head这就是最大的二叉搜索子树头！
    if (getBSTSize(head) != 0) {
      return head;
    }
    // 去左树上找哪个结点是最大二叉搜索子树的头结点
    TreeNode leftAns = maxSubBSTHead1(head.left);
    // 去右树上找哪个结点是最大二叉搜索子树的头结点
    TreeNode rightAns = maxSubBSTHead1(head.right);
    // 左右树哪个二叉搜索子树更大，就返回哪个结点
    return getBSTSize(leftAns) >= getBSTSize(rightAns) ? leftAns : rightAns;
  }

二叉树的递归套路

定义如下数据结构

  public static class Info {
    public TreeNode maxSubBSTHead;
    public int maxSubBSTSize;
    public int min;
    public int max;

    public Info(TreeNode h, int size, int mi, int ma) {
      maxSubBSTHead = h;
      maxSubBSTSize = size;
      min = mi;
      max = ma;
    }
  }

针对每一颗子树，都有如上结构信息，其中

maxSubBSTHead: 表示某个子树的最大二叉搜索子树的头结点

maxSubBSTSize: 表示某个结点如果是二叉搜索树，其大小为多少

min：表示以某个结点为头的树的最小值是多少

max：表示以某个结点为头的树的最大值是多少

接下来定义递归函数

Info process(TreeNode X)

以 X 为头的树，返回对应的 Info

接下来整理可能性

1. 如果 X == null 则直接返回 null，即 base case；

2. 接下来问左树要 Info 信息，再问右树要 Info 信息，整合成 head 的 info 信息，以代码注释来说明

// 问左树要信息
    Info leftInfo = process(X.left);
    // 问右树要信息
    Info rightInfo = process(X.right);
    int min = X.val;
    int max = X.val;
    TreeNode maxSubBSTHead = null;
    int maxSubBSTSize = 0;
    
    if (leftInfo != null) {
      // 左树信息不为 null
      // 则 head.val 和 左树的min PK，谁小谁是以head 为头的min 信息
      min = Math.min(min, leftInfo.min);
      // 则 head.val 和 左树的max PK，谁大谁是以head 为头的max 信息
      max = Math.max(max, leftInfo.max);
      // 以 head 为头的最大二叉搜索子树的头结点至少是leftInfo.maxSubBSTHead
      maxSubBSTHead = leftInfo.maxSubBSTHead;
      // 以 head 为头的最大二叉搜索子树的头结点大小至少是leftInfo.maxSubBSTSize
      maxSubBSTSize = leftInfo.maxSubBSTSize;
    }
    if (rightInfo != null) {
      // 右树信息不为 null 
      // 思路和 左树信息不为 null 一样
      min = Math.min(min, rightInfo.min);
      max = Math.max(max, rightInfo.max);
      if (rightInfo.maxSubBSTSize > maxSubBSTSize) {
        maxSubBSTHead = rightInfo.maxSubBSTHead;
        maxSubBSTSize = rightInfo.maxSubBSTSize;
      }
    }
    // 到了这一步，说明 leftInfo 和 rightInfo 至少有一个为 null
    // 不管哪个为null，如果要以 X 为最大二叉搜索子树的头结点，则需要满足以下条件
    // 1. leftInfo.maxSubBSTHead == X.left && leftInfo.max < X.val
    // 2. rightInfo.maxSubBSTHead == X.right && rightInfo.min > X.val
    if ((leftInfo == null || (leftInfo.maxSubBSTHead == X.left && leftInfo.max < X.val))
        && (rightInfo == null || (rightInfo.maxSubBSTHead == X.right && rightInfo.min > X.val))) {
      maxSubBSTHead = X;
      maxSubBSTSize =
          (leftInfo == null ? 0 : leftInfo.maxSubBSTSize)
              + (rightInfo == null ? 0 : rightInfo.maxSubBSTSize)
              + 1;
    }
    return new Info(maxSubBSTHead, maxSubBSTSize, min, max);

两个思路完整代码如下（含测试代码）

import java.util.ArrayList;

public class Code_MaxSubBSTHead {

  public static class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;

    public TreeNode(int data) {
      this.val = data;
    }
  }

  public static int getBSTSize(TreeNode head) {
    if (head == null) {
      return 0;
    }
    ArrayList<TreeNode> arr = new ArrayList<>();
    in(head, arr);
    for (int i = 1; i < arr.size(); i++) {
      if (arr.get(i).val <= arr.get(i - 1).val) {
        return 0;
      }
    }
    return arr.size();
  }

  public static void in(TreeNode head, ArrayList<TreeNode> arr) {
    if (head == null) {
      return;
    }
    in(head.left, arr);
    arr.add(head);
    in(head.right, arr);
  }

  public static TreeNode maxSubBSTHead1(TreeNode head) {
    if (head == null) {
      return null;
    }
    if (getBSTSize(head) != 0) {
      return head;
    }
    TreeNode leftAns = maxSubBSTHead1(head.left);
    TreeNode rightAns = maxSubBSTHead1(head.right);
    return getBSTSize(leftAns) >= getBSTSize(rightAns) ? leftAns : rightAns;
  }

  public static TreeNode maxSubBSTHead2(TreeNode head) {
    if (head == null) {
      return null;
    }
    return process(head).maxSubBSTHead;
  }

  // 每一棵子树
  public static class Info {
    public TreeNode maxSubBSTHead;
    public int maxSubBSTSize;
    public int min;
    public int max;

    public Info(TreeNode h, int size, int mi, int ma) {
      maxSubBSTHead = h;
      maxSubBSTSize = size;
      min = mi;
      max = ma;
    }
  }

  public static Info process(TreeNode X) {
    if (X == null) {
      return null;
    }
    Info leftInfo = process(X.left);
    Info rightInfo = process(X.right);
    int min = X.val;
    int max = X.val;
    TreeNode maxSubBSTHead = null;
    int maxSubBSTSize = 0;
    if (leftInfo != null) {
      min = Math.min(min, leftInfo.min);
      max = Math.max(max, leftInfo.max);
      maxSubBSTHead = leftInfo.maxSubBSTHead;
      maxSubBSTSize = leftInfo.maxSubBSTSize;
    }
    if (rightInfo != null) {
      min = Math.min(min, rightInfo.min);
      max = Math.max(max, rightInfo.max);
      if (rightInfo.maxSubBSTSize > maxSubBSTSize) {
        maxSubBSTHead = rightInfo.maxSubBSTHead;
        maxSubBSTSize = rightInfo.maxSubBSTSize;
      }
    }
    if ((leftInfo == null ? true : (leftInfo.maxSubBSTHead == X.left && leftInfo.max < X.val))
        && (rightInfo == null
            ? true
            : (rightInfo.maxSubBSTHead == X.right && rightInfo.min > X.val))) {
      maxSubBSTHead = X;
      maxSubBSTSize =
          (leftInfo == null ? 0 : leftInfo.maxSubBSTSize)
              + (rightInfo == null ? 0 : rightInfo.maxSubBSTSize)
              + 1;
    }
    return new Info(maxSubBSTHead, maxSubBSTSize, min, max);
  }

  // for test
  public static TreeNode generateRandomBST(int maxLevel, int maxValue) {
    return generate(1, maxLevel, maxValue);
  }

  // for test
  public static TreeNode generate(int level, int maxLevel, int maxValue) {
    if (level > maxLevel || Math.random() < 0.5) {
      return null;
    }
    TreeNode head = new TreeNode((int) (Math.random() * maxValue));
    head.left = generate(level + 1, maxLevel, maxValue);
    head.right = generate(level + 1, maxLevel, maxValue);
    return head;
  }

  public static void main(String[] args) {
    int maxLevel = 4;
    int maxValue = 100;
    int testTimes = 1000000;
    for (int i = 0; i < testTimes; i++) {
      TreeNode head = generateRandomBST(maxLevel, maxValue);
      if (maxSubBSTHead1(head) != maxSubBSTHead2(head)) {
        System.out.println("Oops!");
      }
    }
    System.out.println("finish!");
  }
}

更多

算法和数据结构笔记