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

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

    作者：Grey

    原文地址：

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

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

    题目描述

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

    暴力解法

    定义递归函数

    TreeNode maxSubBSTHead1(TreeNode head)

    • 1

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

    接下来是 base case，

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

    • 1
    • 2
    • 3

    定义一个辅助函数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();
  }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14

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

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16

    二叉树的递归套路

    定义如下数据结构

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13

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

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

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

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

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

    接下来定义递归函数

    Info process(TreeNode X)

    • 1

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43

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

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


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138

    更多

    算法和数据结构笔记

  • 相关阅读:
    linuxcnc分支machinekit
    Spring更简单的使用方法
    数字化时代，企业如何建立自身的云平台与商业模式的选择？
    搜索中常见数据结构与算法探究（二）
    如何使用远程Linux虚拟机的图形界面
    方案详解|AARRR+八角行为分析=用游戏化思维实现用户增长
    学习nginx的一点记录
    信息学奥赛一本通 1947：【09NOIP普及组】细胞分裂 | 洛谷 P1069 [NOIP2009 普及组] 细胞分裂
    [车联网安全自学篇] Android安全之检测APK中异常处理代码是否暴露敏感信息
    jacoco—增量代码覆盖率实现
  • 原文地址：https://blog.csdn.net/hotonyhui/article/details/128177983