236.Lowest Common Ancestor of a Binary Tree

刺骨的言语ヽ痛彻心扉 2021-10-29 15:54 347阅读 0赞

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

According to the definition of LCA on Wikipedia: “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).”

  1. _______3______
  2.        /              \
  3.     ___5__          ___1__
  4.    /      \        /      \
  5.    6      _2       0       8
  6.          /  \
  7.          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.

方法：递归。如果root为空或者root为p或者q节点，那么直接返回root。递归求左右子树中是否有p和q的最近公共祖先。如果左右子树递归求得的结果均不为空，那么表示p和q分属左右子树，直接返回root，否则p和q均属于左子树或者右子树，那么返回递归求出来的结果。

  1. /**

    • Definition for a binary tree node.
    • struct TreeNode {
    • int val;
    • TreeNode *left;
    • TreeNode *right;
    • TreeNode(int x) : val(x), left(NULL), right(NULL) {}

    • };
      /
      class Solution {
      public:
      TreeNode       lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode* q) {

      1.  if(!root||p==root||q==root)
      2.      return root;
      3.  TreeNode * left =lowestCommonAncestor(root->left,p,q);
      4.  TreeNode * right=lowestCommonAncestor(root->right,p,q);
      5.  if(left&&right)//p和q分属root两边
      6.      return root;
      7.  return left? left:right;//p和q只是位于左右子树之中的一个

      }
      };

转载于:https://www.cnblogs.com/zhoudayang/p/5041425.html

发表评论

表情：
评论列表 （有 0 条评论，347人围观）

还没有评论，来说两句吧...

相关阅读