遞歸算法
遞歸算法通常有兩種路召，一種是自己直接遞歸，另一種是結(jié)合一個(gè)Helper類幫助遞歸晃择，但本質(zhì)上都可以擴(kuò)展為第二種遞歸蛆楞。
例如：尋找兩個(gè)節(jié)點(diǎn)的最低公共祖先就屬于結(jié)合一個(gè)Helper類輔組遞歸
在這個(gè)功能的實(shí)現(xiàn)中使用了findCommonParentNode()和hasNodes()兩個(gè)方法。
findCommonParentNode()是主體類杯道，負(fù)責(zé)邏輯上的實(shí)現(xiàn)：
- 如果兩個(gè)節(jié)點(diǎn)不同時(shí)在左子樹(shù)或右子樹(shù)匪煌，則說(shuō)明當(dāng)前根節(jié)點(diǎn)即為最低公共父節(jié)點(diǎn)；
- 如果兩個(gè)節(jié)點(diǎn)同時(shí)在右子樹(shù)党巾，則進(jìn)一步搜索右子樹(shù)萎庭；
- 如果兩個(gè)節(jié)點(diǎn)同時(shí)在左子樹(shù)，則進(jìn)一步搜索左子樹(shù)齿拂。
hasNodes是輔助類驳规，負(fù)責(zé)具體業(yè)務(wù)的實(shí)現(xiàn)：
- 遍歷給定樹(shù)找到給定的兩個(gè)節(jié)點(diǎn)
/**
* find nodes in leftTree and rightTree respectively
* if both leftTree and rightTree don't have given nodes, it means
* the current root node is the common node, then return the root.
* if given nodes are in leftTree or rightTree, then we find them
* in leftTree or rightTree
* @param node1
* @param node2
* @param root
* @return
*/
public BinaryNode findCommonParentNode(BinaryNode node1, BinaryNode node2, BinaryNode root) {
if (root == null)
return null;
boolean inLeftSubTree = hasNodes(node1, node2, root.left);
boolean inRightSubTree = hasNodes(node1, node2, root.right);
// 如果既不在左子樹(shù)又不在右子樹(shù)，則說(shuō)明當(dāng)前節(jié)點(diǎn)就是最低公共祖先
if (!inLeftSubTree && !inRightSubTree)
return root;
// 如果在左子樹(shù)或者右子樹(shù)中署海，則進(jìn)一步搜索左子樹(shù)或右子樹(shù)
if (inLeftSubTree)
return findCommonParentNode(node1, node2, root.left);
else
return findCommonParentNode(node1, node2, root.right);
}
/**
* This is a level-sequence Traverse to find node1 and node2 in the given tree
* @param node1
* @param node2
* @param root
* @return
*/
private boolean hasNodes(BinaryNode node1, BinaryNode node2, BinaryNode root) {
Queue<BinaryNode> queue = new LinkedList<>();
queue.add(root);
boolean hasNode1 = false;
boolean hasNode2 = false;
while (!queue.isEmpty()) {
BinaryNode node = queue.remove();
// mark node1 and node2
if (node == node1)
hasNode1 = true;
else if (node == node2)
hasNode2 = true;
// given tree has node1 and node2
if (hasNode1 && hasNode2)
return true;
if (node.left != null)
queue.add(node.left);
if (node.right != null)
queue.add(node.right);
}
return false;
}
直接遞歸的有基本的遍歷：
在直接遞歸中業(yè)務(wù)實(shí)現(xiàn)代碼不是那么明顯吗购，容易讓人暈頭轉(zhuǎn)向医男，但只要把握住了遞歸邏輯，實(shí)際上是可以套用第二種遞歸方法的模式的巩搏。
遞歸函數(shù)最終返回的值是又最里層返回值所決定的
preOrder()前序遍歷將主體類和輔助類合并在了一起
前序遍歷要求：
- 首先訪問(wèn)根節(jié)點(diǎn)昨登；
- 有左節(jié)點(diǎn)的時(shí)候訪問(wèn)左節(jié)點(diǎn)趾代；
- 沒(méi)左節(jié)點(diǎn)了訪問(wèn)右節(jié)點(diǎn)贯底；
public void preOrder(BinaryNode root) {
if (root == null)
return null;
// 先訪問(wèn)當(dāng)前節(jié)點(diǎn)
System.out.print(root.val); // 僅僅只是輸出值，但可以替換成更復(fù)雜的邏輯
// 再訪問(wèn)左節(jié)點(diǎn)
preOrder(root.left);
// 再訪問(wèn)右節(jié)點(diǎn)
preOrder(root.right);
}
