二叉树最近公共祖先[逆向思维非模拟逻辑（逻辑整理）]

逻辑整理

前言一、二叉搜索树最近公共祖先二、逆向思维+逻辑整理1、逆向思维2、逻辑整理 总结参考文献

前言

我们编码的时候一般都是按照逻辑顺序进行模拟，这样写出来的代码不够简洁，什么写不出代码。而常见的解决方式就是逆向思维法、逻辑整理法，来应对不同的情况，本文通过二叉搜索树公共祖先为例，练习逆向思维法；并自己提高难度，当该二叉树不是搜索树时，该怎么办？来训练逻辑整理能力。

一、二叉搜索树最近公共祖先

二、逆向思维+逻辑整理

1、逆向思维

target:在二叉搜索树中找指定两节点最近公共祖先。根据二叉搜索树中序遍历有序性，当root.val > p.val && root.val > q.val 时，root = root.left;当root.val < p.val && root.val < q.val 时，root = root.right;否则 表示两个节点一左一右，或者碰到了p.q节点，直接返回root注：这里也称逆向思维法，我们本想这一个节点在左，一个节点在右，就返回这个root，返回这个root是我们的直接目的。但这样判断一个在左一个在右，非常麻烦，先要判断谁大，再要求比root.val大，谁小比root.val小才行。如果先判断该往左走还是右走，留下的就是中间，那么代码就简洁了。总：所以编代码要变通，而不是一味的面向过程的模拟。

public class LowestCommonAncestor {/*target:在二叉搜索树中找指定两节点最近公共祖先。根据二叉搜索树中序遍历有序性，当root.val > p.val && root.val > q.val 时，root = root.left;当root.val < p.val && root.val < q.val 时，root = root.right;否则 表示两个节点一左一右，或者碰到了p.q节点，直接返回root注：这里也称逆向思维法，我们本想这一个节点在左，一个节点在右，就返回这个root，返回这个root是我们的直接目的。但这样判断一个在左一个在右，非常麻烦，先要判断谁大，再要求比root.val大，谁小比root.val小才行。如果先判断该往左走还是右走，留下的就是中间，那么代码就简洁了。总：所以编代码要变通，而不是一味的面向过程的模拟。*/public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {while (root != null) {if (root.val > p.val && root.val > q.val) root = root.left;else if (root.val < p.val && root.val < q.val) root = root.right;else return root;}return null;}// Definition for a binary tree node.public class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int x) {val = x;}}}

2、逻辑整理

// 如果该二叉树不是搜索二叉树，咋办？class LowestCommonAncestor2 {/*target:在二叉树中找指定两节点最近公共祖先。不是二叉搜索树，不能利用左中右特性。可以通过递归拿到root到p的路径，然后去回溯寻找root到q的路径，寻到回溯路径上第一个已经在root到p路径上，则返回。*/public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {Set<TreeNode> path = new HashSet<>();// 填充pathfullPath(root, path, p);// 寻找祖先节点。findAnc(root, path, q);return anc;}TreeNode anc;private boolean findAnc(TreeNode root, Set<TreeNode> path, TreeNode q) {// 递归到null上了或者这条路径上没找到。// 逻辑整理之后的样子，可以自己尝试按照基本寻找路径法来对比一下。// 逻辑整理之后，只有一个ifif (root == null || !(root == q || findAnc(root.left, path, q) || findAnc(root.right, path, q))) return false;if (anc == null && path.contains(root)) anc = root;return true;}private boolean fullPath(TreeNode root, Set<TreeNode> path, TreeNode p) {// 逻辑整理之后，只有一个ifif (root == null || !(root == p || fullPath(root.left, path, p) || fullPath(root.right, path, p))) return false;// 遇到p了，结束递归，开始回溯赋值。(要么是该root为p，要么是子树有p)// 典型的非过程思维，非模拟思维。path.add(root);return true;/*逻辑整理之前:if (root == null) return false;if (root == p) {path.add(root);}boolean flag = fullPath(root.left, path, p);if (flag) {path.add(root);return true;}return fullPath(root.right,path,p);*/}// Definition for a binary tree node.public class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int x) {val = x;}}}

总结

1）逆向思维转复杂为简单。

2）逻辑整理，让代码简洁高效，去掉太多的if。

参考文献

[1] LeetCode 二叉搜索树最近公共祖先