LeetCode - Medium - 236. Lowest Common Ancestor of a Binary Tree

逃离我推掉我的手 2022-10-08 02:30 110阅读 0赞

## Topic ##

*  Tree

## Description ##

[https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/][https_leetcode.com_problems_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 `p` and `q` as the lowest node in `T` that has both `p` and `q` as descendants (where we allow **a node to be a descendant of itself**).”

**Example 1:**  
![023761b7beccfe21c750c1b8faf96073.png][]

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
    Output: 3
    Explanation: The LCA of nodes 5 and 1 is 3.

**Example 2:**  
![023761b7beccfe21c750c1b8faf96073.png][]

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
    Output: 5
    Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

**Example 3:**

Input: root = [1,2], p = 1, q = 2
    Output: 1

**Constraints:**

*  The number of nodes in the tree is in the range  \[ 2 , 1 0 5 \] \[2, 10^5\] \[2,105\].
 *   − 1 0 9 < = N o d e . v a l < = 1 0 9 -10^9 <= Node.val <= 10^9 −109<=Node.val<=109
 *  All `Node.val` are unique.
 *  `p != q`
 *  `p` and `q` will exist in the tree.

## Analysis ##

方法一：自己写的。找出从根节点到两条目标节点路径，然后找出最低公有祖先。

方法二：别人写的。运用二叉树后序遍历模式。

## Submission ##

import java.util.ArrayList;
    import java.util.List;
    
    import com.lun.util.BinaryTree.TreeNode;
    
    public class LowestCommonAncestorOfABinaryTree { 
    	
        @SuppressWarnings("unchecked")
    	public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { 
    		List<TreeNode>[] paths = new List[2];
    		List<TreeNode> path = new ArrayList<>();
    		find(root, p, q, path, paths);
    		
    		int step = Math.min(paths[0].size(), paths[1].size());
    		TreeNode result = null;
    		
    		for(int i = 0 ; i < step; i++) { 
    			if(paths[0].get(i) != paths[1].get(i)) 
    				break;
    			result = paths[0].get(i);
    		}
    		return result;
        }
        
        private void find(TreeNode node, TreeNode p, TreeNode q, List<TreeNode> path, List<TreeNode>[] paths) { 
        	if(node == null || paths[0] != null && paths[1] != null)
        		return;
        	
        	path.add(node);
        	
        	if(node.val == p.val || node.val == q.val) { 
        		if(paths[0] == null) { 
        			paths[0] = new ArrayList<>(path);
        		}else if(paths[1] == null){ 
        			paths[1] = new ArrayList<>(path);
        			return;
        		}
        	}
        	
        	find(node.left, p, q, path, paths);
        	find(node.right, p, q, path, paths);
        	
        	path.remove(path.size() - 1);
        	
        }
        
        public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) { 
            if(root == null || root.val == p.val || root.val == q.val)  return root;
            TreeNode left = lowestCommonAncestor2(root.left, p, q);
            TreeNode right = lowestCommonAncestor2(root.right, p, q);
            if(left != null && right != null)   
            	return root;
            return left != null ? left : right;
        }
        
        
    }

## Test ##

import static org.junit.Assert.*;
    import static com.lun.util.BinaryTree.integers2BinaryTree;
    import org.junit.Test;
    
    import com.lun.util.BinaryTree.TreeNode;
    
    public class LowestCommonAncestorOfABinaryTreeTest { 
    
    	@Test
    	public void test() { 
    		LowestCommonAncestorOfABinaryTree obj = new LowestCommonAncestorOfABinaryTree();
    		TreeNode root1 = integers2BinaryTree(3,5,1,6,2,0,8,null,null,7,4);
    		assertEquals(3, obj.lowestCommonAncestor(root1, n(5), n(1)).val);
    		assertEquals(5, obj.lowestCommonAncestor(root1, n(5), n(4)).val);
    		
    		TreeNode root2 = integers2BinaryTree(1, 2);
    		assertEquals(1, obj.lowestCommonAncestor(root2, n(1), n(2)).val);
    	}
    	
    	@Test
    	public void test2() { 
    		LowestCommonAncestorOfABinaryTree obj = new LowestCommonAncestorOfABinaryTree();
    		TreeNode root1 = integers2BinaryTree(3,5,1,6,2,0,8,null,null,7,4);
    		assertEquals(3, obj.lowestCommonAncestor2(root1, n(5), n(1)).val);
    		assertEquals(5, obj.lowestCommonAncestor2(root1, n(5), n(4)).val);
    		
    		TreeNode root2 = integers2BinaryTree(1, 2);
    		assertEquals(1, obj.lowestCommonAncestor2(root2, n(1), n(2)).val);
    	}
    	
    	private TreeNode n(int val) { 
    		return new TreeNode(val);
    	}
    	
    }

[https_leetcode.com_problems_lowest-common-ancestor-of-a-binary-tree]: https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/
[definition of LCA on Wikipedia]: https://en.wikipedia.org/wiki/Lowest_common_ancestor
[023761b7beccfe21c750c1b8faf96073.png]: /images/20221005/14ced927195b41f5a98b490ea6e68996.png