最低公共祖先LCA

题目

ps：这道题来源是剑指offer第50题；但是变种真的好多啊，所以就记录一下；

####树中两个结点的最低公共祖先：

  1. 首先我们要明白这个最低公共祖先是啥？对于一个结点，它上面能到达他的都叫做祖先，他的父结点和它的父结点的父结点；
  2. 树，因为树的不同，这道题有很多变种；比如二叉树？二叉搜索树，或者只是树；

热身树 oj

有一棵无穷大的满二叉树，其结点按根结点一层一层地从左往右依次编号，根结点编号为1。现在有两个结点a，b。请设计一个算法，求出a和b点的最近公共祖先的编号。
给定两个int a,b。为给定结点的编号。请返回a和b的最近公共祖先的编号。注意这里结点本身也可认为是其祖先。

这个就是比较简化的问题了，满二叉树，根结点为1；那么根结点和子结点一定是2倍的关系；k的两个子结点：2k，2k+1；根据这个关系两个子结点一直除以2，总会变成一的，往前推几步，也总会找到最低祖先的；另一种变形就是通过2进制，因为每次都是二倍，每次都相当于左移了一位，那么两个结点编号的二进制编码前面几位应该保持一致；

1
2
3
4
5
6
7
8
9
public int getLCA1(int a, int b) {
      while (a != b) {
          if (a > b) {
              a >>= 1;
          } else
              b >>= 1;
      }
      return a;
  }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int getLCA2(int a, int b) {
        char [] chars1 = Integer.toBinaryString(a).toCharArray();
        char [] chars2 = Integer.toBinaryString(b).toCharArray();
        int i = 0;
        int sum = 0;
        while (i<chars1.length&&i<chars2.length)
        {
            if (chars1[i] != chars2[i]) {
                break;
            }
            sum = sum*2 +chars1[i] -'0';
            i++;
        }
        return sum;
    }

二叉搜索树 oj

  1. 二叉搜索树的话就很简单了，因为这个排过序，左结点小，右结点大；只有两个结点宽度以内的结点符合比一个大，比另一个小，而最低祖先就是最先找到的；
    比如说这个
    这里写图片描述
    假设我们找 0 ，5 的最低祖先，从上面开始找，很明显先找到的就是2，那就是它了；
1
2
3
4
5
6
7
8
9
10
11
12
13
public TreeNode findLCABST(TreeNode root, TreeNode p, TreeNode q) {
       int a = p.val;
       int b = q.val;
       if (root != null) {
           if (root.val > a && root.val > b)
               findLCABST(root.left, p, q);
           else if (root.val < a && root.val < b)
               findLCABST(root.right, p, q);
           else
               return root;
       }
       return null;
   }

一般二叉树 oj

解法一：我们纠结一下祖先的定义，祖先是什么？祖先就是一个根，他可以遍历到和两个结点，就叫做祖先，于是我们就可以从上往下找；自顶向下

1
2
3
4
5
6
7
8
9
10
11
12
public static TreeNode findLCABT2(TreeNode root, TreeNode p, TreeNode q) {
       /*
       核心想法是这两个结点肯定是祖先的子结点，于是就从root开始寻找；root是祖先，
       然后寻找root的左结点是不是祖先，有右结点是不是祖先；
       最后我们找到，当前结点不是两个结点的祖先，那当前结点的父结点就是最低公共祖先了
        */
       if (hasNode(root.left, p) && hasNode(root.left, q))
           return findLCABT2(root.left, p, q);
       if (hasNode(root.right, p) && hasNode(root.right, q))
           return findLCABT2(root.right, p, q);
       return root;
   }

解法二：自顶向下做完了，我们还会发现好麻烦啊，重复遍历了很多东西，为啥不反过来呢？后序遍历，如果出现结点，就告知父结点，在后序遍历中递归向上返回时，这个信息就向上传递了；我们就知道某个结点的子树中既有结点一，又有结点二，那就是它了；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
       /*
       思路就是，自底向上走，后序遍历，先遍历最底下，如果有目标结点，在后序遍历后面，就层层向上标记，
       说明有结点在这个子树中，假设同时标记了两次，说明当前结点的子树恰好含有两个结点，这样就找到了最低公共祖先；
       在这道题中，left和right就相当于标记；由于每次找到结点就会返回，所以如果一个结点是另一个的父结点，不只有
       一个标记；
        */
       if (root == null) return null;
       if (root == p) return root;
       if (root == q) return root;
       TreeNode left = lowestCommonAncestor(root.left, p, q);
       TreeNode right = lowestCommonAncestor(root.right, p, q);
       if (left == null) return right;
       if (right == null) return left;
       return root;
   }

解法三：其实第二种就是通过一条路径，将含有结点的信息传到上面去，于是我们就可以主动造出链，然后就变成两个链表求公共结点啦；

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
public static TreeNode findLCABT1(TreeNode root, TreeNode p, TreeNode q) {
       ArrayList<TreeNode> path1 = new ArrayList<>();
       ArrayList<TreeNode> path2 = new ArrayList<>();
       //寻找结点一的路径
       findPath(root, p, path1);
       //寻找结点二的路径
       findPath(root, q, path2);
       //两个链表寻找公共结点的部分
       if (path1 == null || path2 == null || path1.size() == 0 || path2.size() == 0)
           return null;
       int i;
       for (i = 0; i < path1.size() && i < path2.size(); i++) {
           p = path1.get(i);
           q = path2.get(i);
           if (p != q)
               break;
       }
       return path1.get(i - 1);
   }
   public static boolean findPath(TreeNode head, TreeNode node, List<TreeNode> path) {
       //寻找路径的递归结束
       if (head == null)
           return false;
       //将当前结点放在链表里
       path.add(head);
       //找到目标结点，就返回
       if (head == node)
           return true;
       //用if包围，只要找到一个，就直接返回，这样就不用全部遍历了
       if (findPath(head.left, node, path))
           return true;
       if (findPath(head.right, node, path))
           return true;
       path.remove(path.size() - 1);
       return false;
   }

收获

  1. 数据结构真的是很神奇的东西呀，一道题有很多种解法；
  2. 沉下心来，慢慢来；
继续跑<br><br>带着赤子的骄傲