LeetCode（算法）- 235. 二叉搜索树的最近公共祖先

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode(int x) { val = x; }* }*/// 解决方案(1)classSolution {
Stack<TreeNode>pStack=newStack<>(), qStack=newStack<>();
Map<TreeNode, Integer>pMap=newHashMap<>(), qMap=newHashMap<>();
publicTreeNodelowestCommonAncestor(TreeNoderoot, TreeNodep, TreeNodeq) {
dfs(root, p.val, pStack, pMap, 0);
dfs(root, q.val, qStack, qMap, 0);
TreeNoderes=common();
returnres;
    }
TreeNodecommon() {
TreeNoderes;
while (!pStack.isEmpty() &&!qStack.isEmpty()) {
TreeNodepe=pStack.peek();
TreeNodeqe=qStack.peek();
if (pe.val==qe.val) {
res=pStack.peek();
pStack.pop();
qStack.pop();
returnres;
            }
if (pMap.get(pe) >qMap.get(qe)) {
pStack.pop();
            } elseif (pMap.get(pe) <qMap.get(qe)) {
qStack.pop();
            } else {
pStack.pop();
qStack.pop();
            }
        }
returnnull;
    }
voiddfs(TreeNodenode, intval, Stack<TreeNode>stack, Map<TreeNode, Integer>map, intl) {
if (node==null) {
return;
        }
if (node.val==val) {
stack.push(node);
map.put(node, l);
        } elseif (node.val>val) {
stack.push(node);
map.put(node, l);
dfs(node.left, val, stack, map, l+1);
        } else {
stack.push(node);
map.put(node, l);
dfs(node.right, val, stack, map, l+1);
        }
    }
}
// 解决方案(2)classSolution {
publicTreeNodelowestCommonAncestor(TreeNoderoot, TreeNodep, TreeNodeq) {
if(p.val>q.val) { // 保证 p.val < q.valTreeNodetmp=p;
p=q;
q=tmp;
        }
while(root!=null) {
if(root.val<p.val) // p,q 都在 root 的右子树中root=root.right; // 遍历至右子节点elseif(root.val>q.val) // p,q 都在 root 的左子树中root=root.left; // 遍历至左子节点elsebreak;
        }
returnroot;
    }
}
// 解决方案(3)classSolution {
publicTreeNodelowestCommonAncestor(TreeNoderoot, TreeNodep, TreeNodeq) {
if(root.val<p.val&&root.val<q.val)
returnlowestCommonAncestor(root.right, p, q);
if(root.val>p.val&&root.val>q.val)
returnlowestCommonAncestor(root.left, p, q);
returnroot;
    }
}