递归算法
递归算法通常有两种，一种是自己直接递归，另一种是结合一个Helper类帮助递归，但本质上都可以扩展为第二种递归。
例如：寻找两个节点的最低公共祖先就属于结合一个Helper类辅组递归
在这个功能的实现中使用了findCommonParentNode()和hasNodes()两个方法。
findCommonParentNode()是主体类，负责逻辑上的实现：
- 如果两个节点不同时在左子树或右子树，则说明当前根节点即为最低公共父节点；
- 如果两个节点同时在右子树，则进一步搜索右子树；
- 如果两个节点同时在左子树，则进一步搜索左子树。
hasNodes是辅助类，负责具体业务的实现：
- 遍历给定树找到给定的两个节点
/**
* 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);
// 如果既不在左子树又不在右子树，则说明当前节点就是最低公共祖先
if (!inLeftSubTree && !inRightSubTree)
return root;
// 如果在左子树或者右子树中，则进一步搜索左子树或右子树
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;
}
直接递归的有基本的遍历：
在直接递归中业务实现代码不是那么明显，容易让人晕头转向，但只要把握住了递归逻辑，实际上是可以套用第二种递归方法的模式的。
递归函数最终返回的值是又最里层返回值所决定的
preOrder()前序遍历将主体类和辅助类合并在了一起
前序遍历要求：
- 首先访问根节点；
- 有左节点的时候访问左节点；
- 没左节点了访问右节点；
public void preOrder(BinaryNode root) {
if (root == null)
return null;
// 先访问当前节点
System.out.print(root.val); // 仅仅只是输出值，但可以替换成更复杂的逻辑
// 再访问左节点
preOrder(root.left);
// 再访问右节点
preOrder(root.right);
}
