[LeetCode] 236. Lowest Common Ancestor of a Binary Tree

轉自LeetCode

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.

<Solution>

這題是 235. Lowest Common Ancestor of a Binary Search Tree  的衍生題

差別在於，這次的 data structure 不是 BST 而是一般的 binary tree 而已

那想法也是使用 recursive 來解(DFS)

想法如下

• 如果能分別在左右兩個子樹，各自找到 v 和 w，那麼當下的 root 就是 LCA

• 如果分別找左右兩個子樹時，只能找到 v 或 w，也就是只能找到一個，那麼就代表 v 和 w 在同一邊，且找到的那個節點就是 LCA

code 如下

Java

	/**
	* Definition for a binary tree node.
	* public class TreeNode {
	* int val;
	* TreeNode left;
	* TreeNode right;
	* TreeNode(int x) { val = x; }
	* }
	*/
	class Solution {
	public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
	if(root == null || root == p || root == q) {
	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 ? right : left;
	}
	}

view raw lowestCommonAncestorOfBinaryTree.java hosted with ❤ by GitHub

kotlin

	/**
	* Definition for a binary tree node.
	* class TreeNode(var `val`: Int = 0) {
	* var left: TreeNode? = null
	* var right: TreeNode? = null
	* }
	*/
	class Solution {
	fun lowestCommonAncestor(root: TreeNode?, p: TreeNode?, q: TreeNode?): TreeNode? {
	if (root == null || root == p || root == q) {
	return root
	}
	val left = lowestCommonAncestor(root!!.left, p, q)
	val right = lowestCommonAncestor(root!!.right, p, q)
	if(left != null && right != null) {
	return root
	}
	return left?.let{it} ?: right
	}
	}

view raw lowest_common_ancestor_of_a_binary_tree.kt hosted with ❤ by GitHub