[leedcode 236] Lowest Common Ancestor of a Binary Tree

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).”

        _______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.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    List<TreeNode> list1;
    List<TreeNode> list2;
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

/*      前序遍历二叉树,查找p和q。
        一旦找到某一节点,就将其返回,不再遍历其子树。
        若某一子树遍历完后都没有找到p或q,则返回null。
        每一次递归完成后,比较当前根节点的左右子树是否找到p或q。
        若左右子树都找到了(p和q分别在左子树和右子树中),返回当前根节点。
        若只有一个子树找到了,另一子树返回为空(p和q都在同一子树中),返回不为空的子树节点(不一定是当前根节点的子树根节点)。
        若两个子树都没找到(p和q都不在该子树中),返回左子树(实则返回null)。*/

        //注意此时lowestCommonAncestor函数返回值意义已经变了,代表从root起点,是否存在两个节点(之一即可)

        /*if(root==null) return null;
        if(p==root||q==root) return root;
        TreeNode left=lowestCommonAncestor(root.left,p,q);
        TreeNode right=lowestCommonAncestor(root.right,p,q);
        if(left!=null&&right!=null){
            return root;
        }
        return left!=null?left:right;*/

        //第二种方法:使用两个链表保存从根节点到指定节点的路径中遍历到的值,然后转变为求两个链表第一个不同的节点
      list1=new ArrayList<TreeNode>();
      list2=new ArrayList<TreeNode>();
      getPath(root,p,list1);
      getPath(root,q,list2);
      int i=0;
      int j=0;
      for(;i<list1.size()&&j<list2.size();i++,j++){
          if(list1.get(i)!=list2.get(j)) break;
      }
      return list1.get(i-1);
    }
    public boolean getPath(TreeNode root,TreeNode p,List<TreeNode> list){
        if(root==null) return false;
        list.add(root);
        if(root==p) return true;
        boolean isExist=false;
        isExist=getPath(root.left,p,list);
        if(!isExist){
            isExist=getPath(root.right,p,list);

        }
         if(!isExist){
             list.remove(list.size()-1);
             return false;
        }else return true;

    }
}
时间: 08-06

[leedcode 236] Lowest Common Ancestor of a Binary Tree的相关文章

235. Lowest Common Ancestor of a Binary Search Tree &amp;&amp; 236. Lowest Common Ancestor of a Binary Tree

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST. 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

LeetCode 236. Lowest Common Ancestor of a Binary Tree; 235. Lowest Common Ancestor of a Binary Search Tree

236. Lowest Common Ancestor of a Binary Tree 递归寻找p或q,如果找到,层层向上返回,知道 root 左边和右边都不为NULL:if (left!=NULL && right!=NULL) return root; 时间复杂度 O(n),空间复杂度 O(H) class Solution { public: TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode*

刷题236. Lowest Common Ancestor of a Binary Tree

一.题目说明 题目236. Lowest Common Ancestor of a Binary Tree,在一个二叉树中找两个节点的最近公共祖先.难度是Medium! 二.我的解答 这个用二叉树的递归遍历,稍加改造即可: class Solution{ public: TreeNode* lowestCommonAncestor(TreeNode* root,TreeNode*p,TreeNode*q){ if(root == NULL) return root; if(root == p |

【LeetCode】236. Lowest Common Ancestor of a Binary Tree

Lowest Common Ancestor of a Binary Tree 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 th

236. Lowest Common Ancestor of a Binary Tree

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

leetcode 236. Lowest Common Ancestor of a Binary Tree

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

LeetCode OJ 236. Lowest Common Ancestor of a Binary Tree

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

(medium)LeetCode 236.Lowest Common Ancestor of a Binary Tree

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

236. Lowest Common Ancestor of a Binary Tree java solutions

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