LC236-中-二叉树的最近公共祖先

1 题目

https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

最近公共祖先的定义为：对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。就是说最近祖先深度最大，高度最低，举例上最接近要目标点

2 思路

刚开始的思路是找目标节点的所有公共节点，找到祖先节点后，加入列表中，从后向前遍历，最有一个相同的就是最近公共祖先节点

那如何找一个节点的所有父亲节点呢？需要二叉树自下向上遍历【回溯】，那么就需要使用二叉树的后序遍历

后序遍历：在子树中招目标节点，如果找到，就将节点放入List中

class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {List<TreeNode> nodes1 = new LinkedList<>();List<TreeNode> nodes2 = new LinkedList<>();findAncestor(root, p, nodes1);findAncestor(root, q, nodes2);if (nodes1.isEmpty() || nodes2.isEmpty()) return null;TreeNode prev = null;int i = nodes1.size() - 1;int j = nodes2.size() - 1;while (i >= 0 && j >= 0) {if (nodes1.get(i).val != nodes2.get(j).val) {return prev;}prev = nodes1.get(i);i--;j--;}return prev;}public TreeNode findAncestor(TreeNode root, TreeNode target, List<TreeNode> nodes) {if (root != null) {TreeNode left = findAncestor(root.left, target, nodes);TreeNode right = findAncestor(root.right, target, nodes);if (left != null) {  // 左孩子中存在nodes.add(root);return left;}if (right != null) {nodes.add(root);return right;}if (root.val == target.val) {nodes.add(root);return root;}}return null;}
}

Note:
找祖先节点的方法：

• 使用后序遍历，在左右子树中查找
• 找祖先节点时，如何判断当前节点是否祖先节点，即在左子树和右子树中找到了目标节点，则当前节点是祖先节点；孩子节点要一直向上返回
• 找祖先时，因为祖先节点有可能是本身，所以第一个将自己加进去，并返回孩子节点

2 优化：使用后序遍历找公共节点

接上：
找祖先节点只判断当前节点是不是一个目标节点的祖先节点。是不是可以在左右子树中同时找孩子节点，如果找到则其为最近公共节点（因为是自底向上查找的）

class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if (root != null) {TreeNode left = lowestCommonAncestor(root.left, p, q);TreeNode right = lowestCommonAncestor(root.right, p, q);// 找到祖先节点if (left != null && right != null) return root;  // 最近公共祖先节点// 找目标节点if (root.val == p.val || root.val == q.val) return root;  // 孩子节点if (left != null) return left;if (right != null) return right;}return null;}
}

Note:

• 与找所有的祖先节点类似，以找到孩子节点作为判断当前节点是否是祖先
• 如果两个孩子都找到了，则当前节点就是最近公共祖先，直接返回（核心）

找公共祖先是二叉树局部扫描还是全局扫描？

【全局扫描】

TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);

在分支处没有提前返回，需要判断两个分时的情况，因此需要全部扫描完二叉树。然后根据左右的情况再返回。

局部扫描的代码

TreeNode left = lowestCommonAncestor(root.left, p, q);
if (left...) return left;
TreeNode right = lowestCommonAncestor(root.right, p, q);
if (right...) return right;

ACM输入输出

class TreeNode{int val;TreeNode left;TreeNode right;TreeNode() {}TreeNode(int val) {this.val = val; }}// Solutionpublic class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);
//        Solution solution = new Solution();while (in.hasNext()) {String[] strNums = in.nextLine().split(" ");List<TreeNode> nodes = new LinkedList<>();for (String strNum: strNums) {if (!strNum.isEmpty()) {if (strNum.equals("null")) {nodes.add(null);} else {nodes.add(new TreeNode(Integer.parseInt(strNum)));}}}TreeNode root = constructTree(nodes);int num1 = Integer.parseInt(in.nextLine());int num2 = Integer.parseInt(in.nextLine());TreeNode p = new TreeNode(num1);TreeNode q = new TreeNode(num2);TreeNode r = solution.lowestCommonAncestor(root, p, q);if (r != null) System.out.println(r.val);else System.out.println("not found!");}}public static TreeNode constructTree(List<TreeNode> nodes) {if (!nodes.isEmpty()) {TreeNode node = nodes.remove(0);if (node != null) {node.left = constructTree(nodes);node.right = constructTree(nodes);}return node;}return null;}
}
/*
test case:
3 5 6 null null 2 7 null null 4 null null 1 0 null null 8
5
6
r = [5]3 5 6 null null 2 7 null null 4 null null 1 0 null null 8
5
1
r = [3]*/

---

参考

https://www.programmercarl.com/0236.二叉树的最近公共祖先.html