Java 图文并茂讲解两种找二叉树的最近公共祖先的方法

Java 图文并茂讲解两种找二叉树的最近公共祖先的方法

目录思路一：先假设这棵树是二叉搜索树思路二：假设该树是用孩子双亲表示法

思路一：先假设这棵树是二叉搜索树

首先我们补充说明一下什么是二叉搜索树：

在二叉搜索树中，对于每一个节点来说，他的左子树中的值都比他小，右子树的中的值都比他大。所以二叉搜索树的中序遍历是一组有序的数据。

对于上述这棵树，假设要求 p q 的最近公共祖先。

那么它有以下情况：

对于普通的二叉树来说，也无非就这几种情况：pq都在左，pq都在右，pq一左一右，pq有一个是根节点。

所以分别递归的去左子树和右子树中找 p q 节点的公共祖先，找到了则返回该节点，没有找到则返回空。

根据上述思路，我们很容易写出代码

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

if(root == null) return null;

// p 为当前树的根节点

if(p == root) return p;

// q 为当前树的根节点

if(q == root) return q;

// 去左子树中找

TreeNode left = lowestCommonAncestor(root.left,p,q);

// 去右子树中找

TreeNode right = lowestCommonAncestor(root.right,p,q);

// 左边右边都找到了

if(left != null && right != null) {

return root;

}

// 左边找到了，右边没找到

if(left != null) {

return left;

}

if(right != null) {

return right;

}

return null;

}

思路二：假设该树是用孩子双亲表示法

每个节点会保存它父亲节点的地址，可以层层网上找，直到找到两链表的第一个交点，该交点就是他们的公共祖先。

而对于普通的二叉树来说，只能层层往下找，不能往上，所以要保留两节点的路径，直到两路径的最后一个相同节点。这里我们用栈来保留两个节点的路径。

先弹出元素多的栈中的元素，然后两个栈再一起弹出，直到要弹出的节点相等，就是其最近公共祖先。

那么这里最大的难点就是存储路径。

这里用栈来存储路径，当遍历到一个节点时，将该节点放入栈中，再递归该节点的左树和右树找，如果找到了则保留路径，没找到则弹出。

假设找下图的p:

先将根节点放入栈，递归root节点的左子树找，找不到则弹出，在右子树中找。

当 root 走到 6 的时候，发现该节点的左右均为空，说明在该子树中没找到目标节点，弹出 6 ，在 5 的右子树中继续找。

同理在 5 的右子树中也找不到，会弹出直到去 3 的右子树找，来到 1 ，找到。

// 用于找节点的路径

public boolean getPath(TreeNode root, TreeNode node, Stack stack) {

if(root == null || node == null) {

return false;

}

// 将当前节点放入栈中

stack.push(root);

if(root.val == node.val) {

return true;// 找到了

}

// 当前节点没找到，去左子树找

boolean flag = getPath(root.left,node,stack);

// 左子树中找到了，直接返回

if(flag) {

return true;

}

// 左子树没找到，去右子树找

flag = getPath(root.right,node,stack);

// 右子树中找到了，直接返回

if(flag) {

return true;

}

// 左右子树都没找到，弹出节点

stack.pop();

return false;

}

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

if(root == null) {

return null;

}

Stack stackp = new Stack<>();

Stack stahttp://ckq = new Stack<>();

// 分别得到 p q 的路径

getPath(root,p,stackp);

getPath(root,q,stackq);

int sizep = stackp.size();

int sizeq = stackq.size();

if(sizep > sizeq) {

int size = sizep - sizeq;

// 弹出元素直至两栈中元素个数相等

while(size > 0) {

stackp.pop();

size--;

}

}else {

int size = sizeq - sizep;

// 弹出元素直至两栈中元素个数相等

while(size > 0) {

stackq.pop();

size--;

}

}

// 一起弹出，直到找到第一个相同的元素

while(!stackp.isEmpty() && !stackq.isEmpty()) {

if(stackp.peek() == stackq.peek()) {

// 找到了，就返回该节点

return stackq.pop();

}else {

stackp.pop();

stackq.pop();

}

}

// 没找到，返回 null

return null;

}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。