AI 助理
备案控制台
开发者社区 云计算 文章 正文

8.二叉树的递归套路

2021-12-29 73
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 8.二叉树的递归套路


二叉树的递归套路
  • 可以解决面试中绝大多数（95%）的二叉树问题尤其是树型dp问题
  • 本质是利用递归遍历二叉树的便利性

小技巧多如牛毛，大技巧就两个：二叉树的递归套路、暴力递归改动态规划的套路

所谓二叉树的递归套路就是在树上做动态规划，什么是动态规划呢？动态规划就是用时间换空间的方式。

二叉树的递归套路

1)假设以X节点为头，假设可以向X左树和X右树要任何信息

2)在上一步的假设下，讨论以X为头节点的树，得到答案的可能性(最重要)

3)列出所有可能性后，确定到底需要向左树和右树要什么样的信息

4)把左树信息和右树信息求全集，就是任何一棵子树都需要返回的信息S

5)递归函数都返回S，每一棵子树都这么要求

6)写代码，在代码中考虑如何把左树的信息和右树信息整合出整棵树的信息

二叉树的递归套路深度实践
【题目1】

给定一颗二叉树的头节点head，返回这颗二叉树是不是平衡二叉树

什么是平衡树：在一棵二叉树中，每一颗子树左树的高度与右树的高度差不超过1

此题满足条件：

  • 1）左树平衡
  • 2）右树平衡
  • 3）左树与右树高度差不超过1
package com.harrison.class08;
public class Code01_IsBalanced {
  public static class Node {
    public int value;
    public Node left;
    public Node right;
    public Node(int data) {
      this.value = data;
    }
  }
  public static class Info {
    public boolean isBalanced;
    public int height;
    public Info(boolean i, int h) {
      isBalanced = i;
      height = h;
    }
  }
  public static Info process(Node x) {
    if (x == null) {
      return new Info(true, 0);
    }
    Info leftInfo = process(x.left);
    Info rightInfo = process(x.right);
    int height = Math.max(leftInfo.height, rightInfo.height) + 1;
    boolean isBalanced = true;
    if (!leftInfo.isBalanced) {
      isBalanced = false;
    }
    if (!rightInfo.isBalanced) {
      isBalanced = false;
    }
    if (Math.abs(leftInfo.height - rightInfo.height) > 1) {
      isBalanced = false;
    }
    return new Info(isBalanced, height);
  }
  public static boolean isBalanced2(Node head) {
    return process(head).isBalanced;
  }
  public static int process1(Node head, boolean[] ans) {
    if (!ans[0] || head == null) {
      return -1;
    }
    int leftHeight = process1(head.left, ans);
    int rightHeight = process1(head.right, ans);
    if (Math.abs(leftHeight - rightHeight) > 1) {
      ans[0] = false;
    }
    return Math.max(leftHeight, rightHeight) + 1;
  }
  public static boolean isBalanced1(Node head) {
    boolean[] ans = new boolean[1];
    ans[0] = true;
    process1(head, ans);
    return ans[0];
  }
  // for test
  public static Node generateRandomBST(int maxLevel, int maxValue) {
    return generate(1, maxLevel, maxValue);
  }
  // for test
  public static Node generate(int level, int maxLevel, int maxValue) {
    if (level > maxLevel || Math.random() < 0.5) {
      return null;
    }
    Node head = new Node((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 = 5;
    int maxValue = 100;
    int testTimes = 1000000;
    for (int i = 0; i < testTimes; i++) {
      Node head = generateRandomBST(maxLevel, maxValue);
      if (isBalanced1(head) != isBalanced2(head)) {
        System.out.println("Oops!");
      }
    }
    System.out.println("finish!");
  }
}
【题目2】

给定一颗二叉树的头结点head，任何两个结点之间都存在距离，返回整颗二叉树的最大距离

package com.harrison.class08;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
public class Code02_MaxDistance {
  public static class Node {
    public int value;
    public Node left;
    public Node right;
    public Node(int data) {
      this.value = data;
    }
  }
  public static int maxDistance1(Node head) {
    if (head == null) {
      return 0;
    }
    ArrayList<Node> arr = getPrelist(head);
    HashMap<Node, Node> parentMap = getParentMap(head);
    int max = 0;
    for (int i = 0; i < arr.size(); i++) {
      for (int j = i; j < arr.size(); j++) {
        max = Math.max(max, distance(parentMap, arr.get(i), arr.get(j)));
      }
    }
    return max;
  }
  public static ArrayList<Node> getPrelist(Node head) {
    ArrayList<Node> arr = new ArrayList<>();
    fillPrelist(head, arr);
    return arr;
  }
  public static void fillPrelist(Node head, ArrayList<Node> arr) {
    if (head == null) {
      return;
    }
    arr.add(head);
    fillPrelist(head.left, arr);
    fillPrelist(head.right, arr);
  }
  public static HashMap<Node, Node> getParentMap(Node head) {
    HashMap<Node, Node> map = new HashMap<>();
    map.put(head, null);
    fillParentMap(head, map);
    return map;
  }
  public static void fillParentMap(Node head, HashMap<Node, Node> parentMap) {
    if (head.left != null) {
      parentMap.put(head.left, head);
      fillParentMap(head.left, parentMap);
    }
    if (head.right != null) {
      parentMap.put(head.right, head);
      fillParentMap(head.right, parentMap);
    }
  }
  public static int distance(HashMap<Node, Node> parentMap, Node o1, Node o2) {
    HashSet<Node> o1Set = new HashSet<>();
    Node cur = o1;
    o1Set.add(cur);
    while (parentMap.get(cur) != null) {
      cur = parentMap.get(cur);
      o1Set.add(cur);
    }
    cur = o2;
    while (!o1Set.contains(cur)) {
      cur = parentMap.get(cur);
    }
    Node lowestAncestor = cur;
    cur = o1;
    int distance1 = 1;
    while (cur != lowestAncestor) {
      cur = parentMap.get(cur);
      distance1++;
    }
    cur = o2;
    int distance2 = 1;
    while (cur != lowestAncestor) {
      cur = parentMap.get(cur);
      distance2++;
    }
    return distance1 + distance2 - 1;
  }
//  public static class Info {
//    public int maxDistance;
//    public int height;
//
//    public Info(int m, int h) {
//      maxDistance=m;
//      height = h;
//    }
//  }
//  
//  public static Info process(Node x) {
//    if(x==null) {
//      return new Info(0,0);
//    }
//    Info leftInfo=process(x.left);
//    Info rightInfo=process(x.right);
//    int height=Math.max(leftInfo.height, rightInfo.height)+1;
//    int maxDistance=Math.max(Math.max(leftInfo.maxDistance, rightInfo.maxDistance), leftInfo.height+rightInfo.height+1);
//    return new Info(maxDistance,height);
//  }
//  
//  public static int maxDistance2(Node head) {
//    return process(head).maxDistance;
//  }
  public static int maxDistance2(Node head) {
    return process(head).maxDistance;
  }
  public static class Info {
    public int maxDistance;
    public int height;
    public Info(int m, int h) {
      maxDistance = m;
      height = h;
    }
  }
  public static Info process(Node x) {
    if (x == null) {
      return new Info(0, 0);
    }
    Info leftInfo = process(x.left);
    Info rightInfo = process(x.right);
    int height = Math.max(leftInfo.height, rightInfo.height) + 1;
    int p1 = leftInfo.maxDistance;
    int p2 = rightInfo.maxDistance;
    int p3 = leftInfo.height + rightInfo.height + 1;
    int maxDistance = Math.max(Math.max(p1, p2), p3);
    return new Info(maxDistance, height);
  }
  // for test
  public static Node generateRandomBST(int maxLevel, int maxValue) {
    return generate(1, maxLevel, maxValue);
  }
  // for test
  public static Node generate(int level, int maxLevel, int maxValue) {
    if (level > maxLevel || Math.random() < 0.5) {
      return null;
    }
    Node head = new Node((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++) {
      Node head = generateRandomBST(maxLevel, maxValue);
      if (maxDistance1(head) != maxDistance2(head)) {
        System.out.println("Oops!");
      }
    }
    System.out.println("finish!");
  }
}
【题目3】

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

搜索二叉树定义：左树比头结点小，右树比头结点大，每颗子树都如此

package com.harrison.class08;
import java.util.ArrayList;
public class Code03_MaxSubBSTSize {
  public static class Node {
    public int value;
    public Node left;
    public Node right;
    public Node(int data) {
      this.value = data;
    }
  }
  public static int getBSTSize(Node head) {
    if (head == null) {
      return 0;
    }
    ArrayList<Node> arr = new ArrayList<>();
    in(head, arr);
    for (int i = 1; i < arr.size(); i++) {
      if (arr.get(i).value <= arr.get(i - 1).value) {
        return 0;
      }
    }
    return arr.size();
  }
  public static void in(Node head, ArrayList<Node> arr) {
    if (head == null) {
      return;
    }
    in(head.left, arr);
    arr.add(head);
    in(head.right, arr);
  }
  public static int maxSubBSTSize1(Node head) {
    if (head == null) {
      return 0;
    }
    int h = getBSTSize(head);
    if (h != 0) {
      return h;
    }
    return Math.max(maxSubBSTSize1(head.left), maxSubBSTSize1(head.right));
  }
//  public static class Info{
//    public boolean isAllBST;
//    public int maxSubBSTSize;
//    public int min;
//    public int max;
//    
//    public Info(boolean is,int size,int mi,int ma) {
//      isAllBST=is;
//      maxSubBSTSize=size;
//      min=mi;
//      max=ma;
//    }
//  }
//
//  public static Info process(Node x) {
//    if(x==null) {
//      return null;
//    }
//    Info leftInfo=process(x.left);
//    Info rightInfo=process(x.right);
//    
//    int min=x.value;
//    int max=x.value;
//    
//    if(leftInfo!=null) {
//      min=Math.min(min, leftInfo.min);
//      max=Math.max(max, leftInfo.max);
//    }
//    if(rightInfo!=null) {
//      min=Math.min(min, rightInfo.min);
//      max=Math.max(max, rightInfo.max);
//    }
//    
//    
//    int maxSubBSTSize=0;
//    if(leftInfo!=null) {
//      maxSubBSTSize=leftInfo.maxSubBSTSize;
//    }
//    if(rightInfo!=null) {
//      maxSubBSTSize=Math.max(maxSubBSTSize, rightInfo.maxSubBSTSize);
//    }
//    boolean isAllBST=false;
//    
//    if(
//      //左树整体需要是搜索二叉树
//      (leftInfo==null?true:leftInfo.isAllBST)
//      &&
//      //右树整体需要是搜索二叉树
//      (rightInfo==null?true:rightInfo.isAllBST)
//      &&
//      //左树最大值<x
//      (leftInfo==null?true:leftInfo.max<x.value)
//      &&
//      //右树最小值>x
//      (rightInfo==null?true:rightInfo.min>x.value)
//    ) {
//      maxSubBSTSize=
//          (leftInfo==null?0:leftInfo.maxSubBSTSize)
//          +
//          (rightInfo==null?0:rightInfo.maxSubBSTSize)
//          +
//          1;
//        isAllBST=true;
//          
//    }
//    return new Info(isAllBST,maxSubBSTSize,min,max);
//  }
//  
//  public static int maxSubBSTSize2(Node head) {
//    if(head==null) {
//      return 0;
//    }
//    return process(head).maxSubBSTSize;
//  }
  public static int maxSubBSTSize2(Node head) {
    if (head == null) {
      return 0;
    }
    return process(head).maxBSTSubtreeSize;
  }
  public static class Info {
    public int maxBSTSubtreeSize;
    public int allSize;
    public int max;
    public int min;
    public Info(int m, int a, int ma, int mi) {
      maxBSTSubtreeSize = m;
      allSize = a;
      max = ma;
      min = mi;
    }
  }
  public static Info process(Node x) {
    if (x == null) {
      return null;
    }
    Info leftInfo = process(x.left);
    Info rightInfo = process(x.right);
    int max = x.value;
    int min = x.value;
    int allSize = 1;
    if (leftInfo != null) {
      max = Math.max(leftInfo.max, max);
      min = Math.min(leftInfo.min, min);
      allSize += leftInfo.allSize;
    }
    if (rightInfo != null) {
      max = Math.max(rightInfo.max, max);
      min = Math.min(rightInfo.min, min);
      allSize += rightInfo.allSize;
    }
    int p1 = -1;
    if (leftInfo != null) {
      p1 = leftInfo.maxBSTSubtreeSize;
    }
    int p2 = -1;
    if (rightInfo != null) {
      p2 = rightInfo.maxBSTSubtreeSize;
    }
    int p3 = -1;
    boolean leftBST = leftInfo == null ? true : (leftInfo.maxBSTSubtreeSize == leftInfo.allSize);
    boolean rightBST = rightInfo == null ? true : (rightInfo.maxBSTSubtreeSize == rightInfo.allSize);
    if (leftBST && rightBST) {
      boolean leftMaxLessX = leftInfo == null ? true : (leftInfo.max < x.value);
      boolean rightMinMoreX = rightInfo == null ? true : (x.value < rightInfo.min);
      if (leftMaxLessX && rightMinMoreX) {
        int leftSize = leftInfo == null ? 0 : leftInfo.allSize;
        int rightSize = rightInfo == null ? 0 : rightInfo.allSize;
        p3 = leftSize + rightSize + 1;
      }
    }
    return new Info(Math.max(p1, Math.max(p2, p3)), allSize, max, min);
  }
  // for test
  public static Node generateRandomBST(int maxLevel, int maxValue) {
    return generate(1, maxLevel, maxValue);
  }
  // for test
  public static Node generate(int level, int maxLevel, int maxValue) {
    if (level > maxLevel || Math.random() < 0.5) {
      return null;
    }
    Node head = new Node((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++) {
      Node head = generateRandomBST(maxLevel, maxValue);
      if (maxSubBSTSize1(head) != maxSubBSTSize2(head)) {
        System.out.println("Oops!");
      }
    }
    System.out.println("finish!");
  }
}
【题目4】

派对的最大快乐值

员工信息的定义如下：

class Employee{
  public int happy;//这名员工可以带来的快乐值
  List<Employee> subordinates;//这名员工有哪些直接下级
}

派对的最大快乐值：

 公司的每个员工都符合Employee类的描述。整个公司的人员结构可以看作是一棵标准的、没有环的多叉树。树的头节点是公司唯一的老板。除老板之外的每个员工都有唯一的直接上级。叶节点是没有任何下属的基层员工(subordinates列表为空)，除基层员工外，每个员工都有一一个或多个直接下级。

package com.harrison.class08;
import java.util.ArrayList;
import java.util.List;
public class Code04_MaxHappy {
  public static class Employee {
    public int happy;
    public List<Employee> nexts;
    public Employee(int h) {
      happy = h;
      nexts = new ArrayList<>();
    }
  }
  public static class Info {
    public int no;
    public int yes;
    public Info(int n, int y) {
      no = n;
      yes = y;
    }
  }
  public static Info process(Employee x) {
    if (x == null) {
      return new Info(0, 0);
    }
    int no = 0;
    int yes = x.happy;
    for (Employee next : x.nexts) {
      Info nextInfo = process(next);
      no += Math.max(nextInfo.no, nextInfo.yes);
      yes += nextInfo.no;
    }
    return new Info(no, yes);
  }
  public static int maxHappy1(Employee boss) {
    if (boss == null) {
      return 0;
    }
    return process1(boss, false);
  }
  // 当前来到的节点叫cur，
  // up表示cur的上级是否来，
  // 该函数含义：
  // 如果up为true，表示在cur上级已经确定来，的情况下，cur整棵树能够提供最大的快乐值是多少？
  // 如果up为false，表示在cur上级已经确定不来，的情况下，cur整棵树能够提供最大的快乐值是多少？
  public static int process1(Employee cur, boolean up) {
    if (up) { // 如果cur的上级来的话，cur没得选，只能不来
      int ans = 0;
      for (Employee next : cur.nexts) {
        ans += process1(next, false);
      }
      return ans;
    } else { // 如果cur的上级不来的话，cur可以选，可以来也可以不来
      int p1 = cur.happy;
      int p2 = 0;
      for (Employee next : cur.nexts) {
        p1 += process1(next, true);
        p2 += process1(next, false);
      }
      return Math.max(p1, p2);
    }
  }
  public static int maxHappy2(Employee head) {
    Info allInfo = process(head);
    return Math.max(allInfo.no, allInfo.yes);
  }
  public static Employee genarateBoss(int maxLevel, int maxNexts, int maxHappy) {
    if (Math.random() < 0.02) {
      return null;
    }
    Employee boss = new Employee((int) (Math.random() * (maxHappy + 1)));
    genarateNexts(boss, 1, maxLevel, maxNexts, maxHappy);
    return boss;
  }
  // for test
  public static void genarateNexts(Employee e, int level, int maxLevel, int maxNexts, int maxHappy) {
    if (level > maxLevel) {
      return;
    }
    int nextsSize = (int) (Math.random() * (maxNexts + 1));
    for (int i = 0; i < nextsSize; i++) {
      Employee next = new Employee((int) (Math.random() * (maxHappy + 1)));
      e.nexts.add(next);
      genarateNexts(next, level + 1, maxLevel, maxNexts, maxHappy);
    }
  }
  public static void main(String[] args) {
    int maxLevel = 4;
    int maxNexts = 7;
    int maxHappy = 100;
    int testTimes = 100000;
    for (int i = 0; i < testTimes; i++) {
      Employee boss = genarateBoss(maxLevel, maxNexts, maxHappy);
      if (maxHappy1(boss) != maxHappy2(boss)) {
        System.out.println("Oops!");
      }
    }
    System.out.println("finish!");
  }
}
【题目5】

给定一棵二叉树的头节点head，返回这颗二叉树是不是满二叉树

package com.harrison.class08;
public class Code05_IsFull {
  public static class Node {
    public int value;
    public Node left;
    public Node right;
    public Node(int data) {
      this.value = data;
    }
  }
  public static class Info {
    public int height;
    public int nodes;
    public Info(int h, int n) {
      height = h;
      nodes = n;
    }
  }
  public static Info process(Node head) {
    if (head == null) {
      return new Info(0, 0);
    }
    Info leftInfo = process(head.left);
    Info rightInfo = process(head.right);
    int height = Math.max(leftInfo.height, rightInfo.height) + 1;
    int nodes = leftInfo.nodes + rightInfo.nodes + 1;
    return new Info(height, nodes);
  }
  public static boolean isFull1(Node head) {
    if (head == null) {
      return true;
    }
    int height = h(head);
    int nodes = n(head);
    return (1 << height) - 1 == nodes;
  }
  public static int h(Node head) {
    if (head == null) {
      return 0;
    }
    return Math.max(h(head.left), h(head.right)) + 1;
  }
  public static int n(Node head) {
    if (head == null) {
      return 0;
    }
    return n(head.left) + n(head.right) + 1;
  }
  public static boolean isFull2(Node head) {
    if (head == null) {
      return true;
    }
    Info all = process(head);
    return (1 << all.height) - 1 == all.nodes;
  }
  public static Node generateRandomBST(int maxLevel, int maxValue) {
    return generate(1, maxLevel, maxValue);
  }
  // for test
  public static Node generate(int level, int maxLevel, int maxValue) {
    if (level > maxLevel || Math.random() < 0.5) {
      return null;
    }
    Node head = new Node((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 = 5;
    int maxValue = 100;
    int testTimes = 1000000;
    for (int i = 0; i < testTimes; i++) {
      Node head = generateRandomBST(maxLevel, maxValue);
      if (isFull1(head) != isFull2(head)) {
        System.out.println("Oops!");
      }
    }
    System.out.println("finish!");
  }
}
【题目6】

给定一棵二叉树的头节点head，返回这颗二叉树中是不是完全二叉树

列可能性：如果四种情况都不符合，必不是完全二叉树，如果有一种情况成立，就是

  • 1）满二叉树（无缺口）
  • 2）左树是完全二叉树，右树是满二叉树，并且左树高度比右树高度大1
  • 3）左树是满二叉树，右树是满二叉树，且左树高度比右树高度大1
  • 4）左树是满二叉树，右树是完全二叉树，且两边高度一样
package com.harrison.class08;
import java.util.LinkedList;
public class Code06_IsCBT {
  public static class Node {
    public int value;
    public Node left;
    public Node right;
    public Node(int data) {
      this.value = data;
    }
  }
  // 对每一颗子树，是否是满二叉树、是否是完全二叉树、高度多少
  public static class Info {
    public boolean isFull;
    public boolean isCBT;
    public int height;
    public Info(boolean full, boolean cbt, int h) {
      isFull = full;
      isCBT = cbt;
      height = h;
    }
  }
  public static Info process(Node x) {
    if (x == null) {
      return new Info(true, true, 0);
    }
    Info leftInfo = process(x.left);
    Info rightInfo = process(x.right);
    int height = Math.max(leftInfo.height, rightInfo.height) + 1;
    boolean isFull = leftInfo.isFull && rightInfo.isFull && leftInfo.height == rightInfo.height;
    boolean isCBT = false;
    if (isFull) {
      isCBT = true;
    } else {// 以x为头整棵树，不满
      if (leftInfo.isCBT && rightInfo.isCBT) {
        if (leftInfo.isCBT && rightInfo.isFull && leftInfo.height == rightInfo.height + 1) {
          isCBT = true;
        }
        if (leftInfo.isFull && rightInfo.isFull && leftInfo.height == rightInfo.height + 1) {
          isCBT = true;
        }
        if (leftInfo.isFull && rightInfo.isCBT && leftInfo.height == rightInfo.height) {
          isCBT = true;
        }
      }
    }
    return new Info(isFull, isCBT, height);
  }
  public static boolean isCBT1(Node head) {
    if (head == null) {
      return true;
    }
    LinkedList<Node> queue = new LinkedList<>();
    // 是否遇到过左右两个孩子不双全的节点
    boolean leaf = false;
    Node l = null;
    Node r = null;
    queue.add(head);
    while (!queue.isEmpty()) {
      head = queue.poll();
      l = head.left;
      r = head.right;
      if (
      // 如果遇到了不双全的节点之后，又发现当前节点不是叶节点
      (leaf && (l != null || r != null)) || (l == null && r != null)
      ) {
        return false;
      }
      if (l != null) {
        queue.add(l);
      }
      if (r != null) {
        queue.add(r);
      }
      if (l == null || r == null) {
        leaf = true;
      }
    }
    return true;
  }
  public static boolean isCBT2(Node head) {
    if (head == null) {
      return true;
    }
    return process(head).isCBT;
  }
  // for test
  public static Node generateRandomBST(int maxLevel, int maxValue) {
    return generate(1, maxLevel, maxValue);
  }
  // for test
  public static Node generate(int level, int maxLevel, int maxValue) {
    if (level > maxLevel || Math.random() < 0.5) {
      return null;
    }
    Node head = new Node((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 = 5;
    int maxValue = 100;
    int testTimes = 1000000;
    for (int i = 0; i < testTimes; i++) {
      Node head = generateRandomBST(maxLevel, maxValue);
      if (isCBT1(head) != isCBT2(head)) {
        System.out.println("Oops!");
      }
    }
    System.out.println("finish!");
  }
}
【题目7】

给定一棵二叉树的头节点head,和另外两个节点a和b。返回a和b的最低公共祖先

最低公共祖先：a和b往上走初次交汇的点

  • 1）o1和o2都不在x上
  • 2）o1和o2只有一个在x上
  • 3）o1和o2都在以x为头结点的树上    
  • 1> 左树右树各一个
  • 2> 左树有两个
  • 3> 右树有两个
  • 4> x自己是o1或o2

左树右树各返回三个信息：

  • 1）o1和o2最初交汇点，没有交汇点返回null
  • 2）在子树上是否发现o1
  • 3）在子树上是否发现o2
package com.harrison.class08;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
public class Code07_LowestAncestor {
  public static class Node {
    public int value;
    public Node left;
    public Node right;
    public Node(int data) {
      this.value = data;
    }
  }
  public static class Info {
    public Node ans;
    public boolean findA;
    public boolean findB;
    public Info(Node an, boolean fA, boolean fB) {
      ans = an;
      findA = fA;
      findB = fB;
    }
  }
  public static Info process(Node x, Node a, Node b) {
    if (x == null) {
      return new Info(null, false, false);
    }
    Info leftInfo = process(x.left, a, b);
    Info rightInfo = process(x.right, a, b);
    boolean findA = (x == a) || leftInfo.findA || rightInfo.findA;
    boolean findB = (x == b) || leftInfo.findB || rightInfo.findB;
    Node ans = null;
    if (leftInfo.ans != null) {
      ans = leftInfo.ans;
    } else if (rightInfo.ans != null) {
      ans = rightInfo.ans;
    } else {
      if (findA && findB) {
        ans = x;
      }
    }
    return new Info(ans, findA, findB);
  }
  public static Node lowestAncestor1(Node head, Node o1, Node o2) {
    if (head == null) {
      return null;
    }
    // key的父节点是value
    HashMap<Node, Node> parentMap = new HashMap<>();
    parentMap.put(head, null);
    fillParentMap(head, parentMap);
    HashSet<Node> o1Set = new HashSet<>();
    Node cur = o1;
    o1Set.add(cur);
    while (parentMap.get(cur) != null) {
      cur = parentMap.get(cur);
      o1Set.add(cur);
    }
    cur = o2;
    while (!o1Set.contains(cur)) {
      cur = parentMap.get(cur);
    }
    return cur;
  }
  public static void fillParentMap(Node head, HashMap<Node, Node> parentMap) {
    if (head.left != null) {
      parentMap.put(head.left, head);
      fillParentMap(head.left, parentMap);
    }
    if (head.right != null) {
      parentMap.put(head.right, head);
      fillParentMap(head.right, parentMap);
    }
  }
  public static Node lowestAncestor2(Node head, Node a, Node b) {
    return process(head, a, b).ans;
  }
  // for test
  public static Node generateRandomBST(int maxLevel, int maxValue) {
    return generate(1, maxLevel, maxValue);
  }
  // for test
  public static Node generate(int level, int maxLevel, int maxValue) {
    if (level > maxLevel || Math.random() < 0.5) {
      return null;
    }
    Node head = new Node((int) (Math.random() * maxValue));
    head.left = generate(level + 1, maxLevel, maxValue);
    head.right = generate(level + 1, maxLevel, maxValue);
    return head;
  }
  // for test
  public static Node pickRandomOne(Node head) {
    if (head == null) {
      return null;
    }
    ArrayList<Node> arr = new ArrayList<>();
    fillPrelist(head, arr);
    int randomIndex = (int) (Math.random() * arr.size());
    return arr.get(randomIndex);
  }
  // for test
  public static void fillPrelist(Node head, ArrayList<Node> arr) {
    if (head == null) {
      return;
    }
    arr.add(head);
    fillPrelist(head.left, arr);
    fillPrelist(head.right, arr);
  }
  public static void main(String[] args) {
    int maxLevel = 4;
    int maxValue = 100;
    int testTimes = 1000000;
    for (int i = 0; i < testTimes; i++) {
      Node head = generateRandomBST(maxLevel, maxValue);
      Node o1 = pickRandomOne(head);
      Node o2 = pickRandomOne(head);
      if (lowestAncestor1(head, o1, o2) != lowestAncestor2(head, o1, o2)) {
        System.out.println("Oops!");
      }
    }
    System.out.println("finish!");
  }
}

   


爱敲代码的Harrison
目录
相关文章
qiuqiushuibx
|
算法
代码随想录 Day11 二叉树 LeetCode T144,145,94 前中后序遍历 (递归解法)
代码随想录 Day11 二叉树 LeetCode T144,145,94 前中后序遍历 (递归解法)
qiuqiushuibx
55 0
niceffking
|
8月前
|
Java Python
汉诺塔递归问题，递归思路详解
汉诺塔递归问题，递归思路详解
niceffking
132 0
鸽芷咕
|
8月前
|
算法
递归算法：二叉树前序、中序、后序遍历解析与递归思想深度剖析
递归算法：二叉树前序、中序、后序遍历解析与递归思想深度剖析
鸽芷咕
184 0
DarkFire
二叉树相关问题细谈递归（下）
二叉树相关问题细谈递归（下）
DarkFire
71 0
DarkFire
|
存储
二叉树相关问题细谈递归（上）
二叉树相关问题细谈递归
DarkFire
83 0
清水加冰
|
存储
【二叉树】——链式结构（快速掌握递归与刷题技巧）
【二叉树】——链式结构（快速掌握递归与刷题技巧）
清水加冰
186 0
程序员牛哥
|
算法 程序员
彻底搞懂递归的时间复杂度
彻底搞懂递归的时间复杂度
程序员牛哥
388 0
程序员牛哥
|
算法 程序员
让你彻底搞懂递归时间复杂度
让你彻底搞懂递归时间复杂度
程序员牛哥
140 0
BookSea
|
Java
java实现树的前序遍历，递归和非递归实现（简单明了）
java实现树的前序遍历，递归和非递归实现（简单明了）
BookSea
114 0
Mindtechnist
|
算法 C++
【栈的应用】二叉树非递归中序遍历思想解析及代码实现
【栈的应用】二叉树非递归中序遍历思想解析及代码实现
Mindtechnist
222 0
【栈的应用】二叉树非递归中序遍历思想解析及代码实现

热门文章

最新文章

  • 1
    ip查询显示泛播是什么意思？
  • 2
    charles抓包显示乱码解决方法
  • 3
    持续定义SaaS模式云数据仓库+数据银行
  • 4
    从0开始打造一款APP：前端+搭建本机服务，定制暖冬卫衣先到先得
  • 5
    patch 命令用法详解（转）
  • 6
    小程序审核常见驳回类型
  • 7
    评测：AI客服接入钉钉与微信的对比分析
  • 8
    Linux的归档及压缩，Linux的cron时间计划任务， NTP网络时间协议 ， 查看网络连接
  • 9
    全新Gmail网络钓鱼攻击出现 最细心的用户也可能上当
  • 10
    Eclipse内存监控插件 FreeMem
  • 1
    TransPixar AI
    115
  • 2
    《docker基础篇：2.Docker安装》包括前提说明、Docker的基本组成、Docker平台架构图解(架构版)、安装步骤、阿里云镜像加速、永远的HelloWorld、底层原理
    114
  • 3
    通义万相2.1：VBench榜单荣登第一！阿里通义万相最新视频生成模型，支持生成1080P长视频
    56
  • 4
    GLM-Zero：智谱AI推出与 OpenAI-o1-Preview 旗鼓相当的深度推理模型，开放在线免费使用和API调用
    49
  • 5
    DeepSeek Artifacts：在线实时预览的前端 AI 编程工具，基于DeepSeek V3快速生成React App
    50
  • 6
    智能运维新时代：AI在云资源管理中的应用与实践
    43
  • 7
    假如AI欺骗了你 | AI大咖说
    111
  • 8
    写在最前的话
    39
  • 9
    深度强化学习实战：训练DQN模型玩超级马里奥兄弟
    109
  • 10
    体验《多模态数据信息提取》
    37

    • 相关电子书

    更多
  • 低代码开发师（初级）实战教程
  • 冬季实战营第三期：MySQL数据库进阶实战
  • 阿里巴巴DevOps 最佳实践手册
    • 下一篇
    DataWorks智能交互式数据开发与分析之旅