最近真是多事之秋垂蜗，好好的日更被斷了，計(jì)劃永遠(yuǎn)是趕不上變化的解幽，乘著睡前補(bǔ)上吧贴见。
查找給定兩個(gè)節(jié)點(diǎn)最下公共祖先，俗稱LCA算法躲株。
題目介紹
給定任意一個(gè)二叉樹(shù)片部，以及兩個(gè)節(jié)點(diǎn)，查找它們最小公共祖先霜定。題目比較容易理解档悠，就不補(bǔ)圖了廊鸥。
實(shí)現(xiàn)思路
先用暴力算法來(lái)實(shí)現(xiàn)吧，具體流程如下：
1辖所、先定義兩個(gè)節(jié)點(diǎn)List惰说，分別用來(lái)存放給定兩個(gè)節(jié)點(diǎn)的路徑上所有節(jié)點(diǎn)。
2缘回、分別遞歸遍歷兩次樹(shù)助被，將路徑填充到上述定義的List中。
3切诀、最后將根節(jié)點(diǎn)加入到List尾部揩环，因?yàn)槁窂奖囟ò?jié)點(diǎn)，所以最大的公共祖先就是根節(jié)點(diǎn)幅虑。
4丰滑、此時(shí)兩個(gè)List的順序?yàn)槁窂焦?jié)點(diǎn)的倒敘，因此我們只要使用兩個(gè)for循環(huán)找到第一個(gè)相等的節(jié)點(diǎn)就是所要求的解倒庵。
實(shí)現(xiàn)代碼
public class SolutionLCA {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
List<TreeNode> lPath = new ArrayList<>();
List<TreeNode> rPath = new ArrayList<>();
fill(root, p, lPath);
fill(root, q, rPath);
lPath.add(root);
rPath.add(root);
for (TreeNode lTreeNode : lPath) {
for (TreeNode rTreeNode : rPath) {
if (lTreeNode.val == rTreeNode.val) {
return lTreeNode;
}
}
}
return root;
}
public boolean fill(TreeNode root, TreeNode s, List<TreeNode> path) {
if (null == root) {
return false;
}
if (root.val == s.val) {
return true;
}
boolean lExists = fill(root.left, s, path);
if (lExists) {
path.add(root.left);
return true;
}
boolean rExists = fill(root.right, s, path);
if (rExists) {
path.add(root.right);
return true;
}
return false;
}
}
算法相關(guān)實(shí)現(xiàn)源碼地址：https://github.com/xiekq/rubs-algorithms
