我已经编写了一个代码,用于查找二叉树中最小公共节点的祖先节点,但它似乎返回null
而不是LCA。二叉树的LCA问题
我的算法如下。
- 递归发现在树
其中左以及右树已匹配在LCA元件A节点的左和右分支中的祖先。
public class LCA { public static BinaryTreeNode findLCA(BinaryTreeNode root, BinaryTreeNode node1 , BinaryTreeNode node2) { if (root == null) { return null; } BinaryTreeNode left = root.getLeft(); BinaryTreeNode right = root.getRight(); if (left != null && (left == node1 || left == node2)) { return root; } if (right != null && (right == node1 || right == node2)) { return root; } if ((findLCA(left, node1, node2) != null) && (findLCA(right, node1, node2) != null)) { return root; } return null; }}
什么能与此代码的问题?
'但这不行 - “你遇到什么不受欢迎的行为? – amit
@amit,这不是返回给我的lca,而是返回null – Manish
算法效率非常低。改为尝试以下方法:从节点1和节点2将树中向上的路径收集到根节点。然后比较从结尾开始的两个列表以查找两个列表中存在的最后一个项目。这是最接近的共同祖先,复杂度只是O(深度(树)),在平衡二叉树中是O(log n),而在最坏的情况下,你的方法可能在O(n)中运行。当然,如果您没有将反向链接组成一个父节点,我的方法将无法工作。 – Sebastian