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

8.二叉树的递归套路

2021-12-29 67
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 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
目录
相关文章
niceffking
|
5月前
|
Java Python
汉诺塔递归问题，递归思路详解
汉诺塔递归问题，递归思路详解
niceffking
65 0
qiuqiushuibx
|
算法
代码随想录 Day11 二叉树 LeetCode T144,145,94 前中后序遍历 (递归解法)
代码随想录 Day11 二叉树 LeetCode T144,145,94 前中后序遍历 (递归解法)
qiuqiushuibx
45 0
鸽芷咕
|
5月前
|
算法
递归算法：二叉树前序、中序、后序遍历解析与递归思想深度剖析
递归算法：二叉树前序、中序、后序遍历解析与递归思想深度剖析
鸽芷咕
77 0
DarkFire
|
11月前
|
存储
二叉树相关问题细谈递归（上）
二叉树相关问题细谈递归
DarkFire
67 0
DarkFire
|
11月前
二叉树相关问题细谈递归（下）
二叉树相关问题细谈递归（下）
DarkFire
59 0
BookSea
|
Java
java实现树的前序遍历，递归和非递归实现（简单明了）
java实现树的前序遍历，递归和非递归实现（简单明了）
BookSea
99 0
ab6brphvc5lw6
二叉树的前序遍历---递归解法(简单难度）
二叉树的前序遍历---递归解法(简单难度）
ab6brphvc5lw6
79 0
二叉树的前序遍历---递归解法(简单难度）
ab6brphvc5lw6
二叉树的中序遍历---递归解法(简单难度)
二叉树的中序遍历---递归解法(简单难度)
ab6brphvc5lw6
89 0
二叉树的中序遍历---递归解法(简单难度)
ab6brphvc5lw6
|
算法
二叉树的后序遍历---递归解法(简单难度)
二叉树的后序遍历---递归解法(简单难度)
ab6brphvc5lw6
73 0
不断前进的皮卡丘
|
算法
二叉树的遍历方式(递归)
二叉树的遍历方式(递归)
不断前进的皮卡丘
123 0
二叉树的遍历方式(递归)