最近公共祖先 · Lowest Common Ancestor

［抄题］：

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

“The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

      _______3______

     /              \

    ___5__          ___1__

   /      \        /      \

   6      _2       0       8

         /  \

         7   4

For example, the lowest common ancestor (LCA) of nodes 5 and 1 is 3. Another example is LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

［思维问题］：

不知道子节点怎么用dc。直接对给出的p,q节点进行操作即可。

［一句话思路］：

左右分开谁不空返回谁

［输入量］：空：正常情况：特大：特小：程序里处理到的特殊情况：异常情况（不合法不合理的输入）：

［画图］：

［一刷］：

(left != null && right != null) 时，返回的是root节点的结果，不需要再做递归运算了。是一个“合”的过程。

［二刷］：

［三刷］：

［四刷］：

［五刷］：

［总结］：

［复杂度］：Time complexity: O(n) Space complexity: O(n)

［英文数据结构，为什么不用别的数据结构］：

只有dc算法，没有数据结构

［其他解法］：

自己写traverse函数：不好，会形成全局变量

［Follow Up］：

有parent指针的：用对齐的方法做

［LC给出的题目变变变］：

Lowest Common Ancestor of a Binary Search Tree 一模一样的，约束条件没用，直接套。

public class Solution {

    /*

     * @param root: The root of the binary search tree.

     * @param A: A TreeNode in a Binary.

     * @param B: A TreeNode in a Binary.

     * @return: Return the least common ancestor(LCA) of the two nodes.

     */

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode A, TreeNode B) {

        if (root == null || A == root || B == root) {//

            return root;

        }

        //divide

        TreeNode left = lowestCommonAncestor(root.left, A, B);

        TreeNode right = lowestCommonAncestor(root.right, A, B);

        //conquer

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

            return root;//

        }

        else if (left != null) {

            return left;

        }

        else if (right != null) {

            return right;

        }

        else {

            return null;

        }

    }

}

巴特西

最近公共祖先 · Lowest Common Ancestor

最新文章

热门文章