LeetCode - Medium - 1123. Lowest Common Ancestor of Deepest Leaves

不念不忘少年蓝@ 2022-10-09 02:49 12阅读 0赞

## Topic ##

*  Tree
 *  Depth-first Search

## Description ##

[https://leetcode.com/problems/lowest-common-ancestor-of-deepest-leaves/][https_leetcode.com_problems_lowest-common-ancestor-of-deepest-leaves]

Given the `root` of a binary tree, return the lowest common ancestor of its deepest leaves.

Recall that:

*  The node of a binary tree is a leaf if and only if it has no children
 *  The depth of the root of the tree is `0`. if the depth of a node is `d`, the depth of each of its children is `d + 1`.
 *  The lowest common ancestor of a set `S` of nodes, is the node `A` with the largest depth such that every node in `S` is in the subtree with root `A`.

**Note:** This question is the same as 865: [https://leetcode.com/problems/smallest-subtree-with-all-the-deepest-nodes/][https_leetcode.com_problems_smallest-subtree-with-all-the-deepest-nodes]

**Example 1:**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE4NjMwMjQ_size_16_color_FFFFFF_t_70_pic_center]

Input: root = [3,5,1,6,2,0,8,null,null,7,4]
    Output: [2,7,4]
    Explanation: We return the node with value 2, colored in yellow in the diagram.
    The nodes coloured in blue are the deepest leaf-nodes of the tree.
    Note that nodes 6, 0, and 8 are also leaf nodes, but the depth of them is 2, but the depth of nodes 7 and 4 is 3.

**Example 2:**

Input: root = [1]
    Output: [1]
    Explanation: The root is the deepest node in the tree, and it's the lca of itself.

**Example 3:**

Input: root = [0,1,3,null,2]
    Output: [2]
    Explanation: The deepest leaf node in the tree is 2, the lca of one node is itself.

**Constraints:**

*  The number of nodes in the tree will be in the range  \[ 1 , 1000 \] \[1, 1000\] \[1,1000\].
 *   0 < = N o d e . v a l < = 1000 0 <= Node.val <= 1000 0<=Node.val<=1000
 *  The values of the nodes in the tree are **unique**.

## Analysis ##

受[LeetCode - Medium - 236. Lowest Common Ancestor of a Binary Tree][]启发。

方法一：自己写的，用后序遍历模式

方法二：别人写的，用后序遍历模式

## Submission ##

import com.lun.util.BinaryTree.TreeNode;
    
    public class LowestCommonAncestorOfDeepestLeaves { 
        
    	//方法一：自己写的，用后序遍历模式
        public TreeNode lcaDeepestLeaves(TreeNode root) { 
        	Object[] result = lcaDeepestLeaves(root, 0);
        	return result != null ? (TreeNode)result[0] : null;
        }
        
        private Object[] lcaDeepestLeaves(TreeNode node, int depth) { 
        	if(node == null) return null;
        	
        	depth++;
        	
        	Object[] leftResult = lcaDeepestLeaves(node.left, depth);
        	Object[] rightResult = lcaDeepestLeaves(node.right, depth);
        	
        	if(leftResult == null && rightResult == null) { //叶子节点
        		return new Object[] { node, depth};
        	}else if(leftResult != null && rightResult == null){ 
        		return leftResult;
        	}else if(leftResult == null && rightResult != null) { 
        		return rightResult;
        	}else { 
        		int leftDepth = (int)leftResult[1];
        		int rightDepth = (int)rightResult[1];
        		
        		if(leftDepth > rightDepth) { 
        			return leftResult; 
        		}else if(leftDepth < rightDepth) { 
        			return rightResult;
        		}else { 
        			leftResult[0] = node;
        			return leftResult;
        		}
        	}
        }
    	
        //方法二：别人写的，用后序遍历模式
        public TreeNode lcaDeepestLeaves2(TreeNode root) { 
            Pair p = getLca(root, 0);
            return p.node;
        }
        
        private Pair getLca(TreeNode root, int d) { 
            if (root == null) return new Pair(null, d);
            Pair l = getLca(root.left, d + 1);
            Pair r = getLca(root.right, d + 1);
            if (l.d == r.d) { 
                return new Pair(root, l.d);
            } else { 
                return  l.d > r.d ? l : r;
            }
        }
        
        private class Pair { 
        	TreeNode node;
        	int d;
        	Pair(TreeNode node, int d) { 
        		this.node = node;
        		this.d = d;
        	}
        }
    }

## Test ##

import static org.junit.Assert.*;
    import org.junit.Test;
    
    import com.lun.util.BinaryTree;
    import com.lun.util.BinaryTree.TreeNode;
    
    public class LowestCommonAncestorOfDeepestLeavesTest { 
    
        @Test
        public void test() { 
            LowestCommonAncestorOfDeepestLeaves lObj = new LowestCommonAncestorOfDeepestLeaves();
    
            TreeNode root1 = BinaryTree.integers2BinaryTree(3,5,1,6,2,0,8,null,null,7,4);
            TreeNode expected1 = BinaryTree.integers2BinaryTree(2,7,4);
            assertTrue(BinaryTree.equals(lObj.lcaDeepestLeaves(root1), expected1));
            
            TreeNode root2 = BinaryTree.integers2BinaryTree(1);
            TreeNode expected2 = BinaryTree.integers2BinaryTree(1);
            assertTrue(BinaryTree.equals(lObj.lcaDeepestLeaves(root2), expected2));
            
            TreeNode root3 = BinaryTree.integers2BinaryTree(0,1,3,null,2);
            TreeNode expected3 = BinaryTree.integers2BinaryTree(2);
            assertTrue(BinaryTree.equals(lObj.lcaDeepestLeaves(root3), expected3));
            
        }
        
        @Test
        public void test2() { 
        	LowestCommonAncestorOfDeepestLeaves lObj = new LowestCommonAncestorOfDeepestLeaves();
        	
        	TreeNode root1 = BinaryTree.integers2BinaryTree(3,5,1,6,2,0,8,null,null,7,4);
        	TreeNode expected1 = BinaryTree.integers2BinaryTree(2,7,4);
        	assertTrue(BinaryTree.equals(lObj.lcaDeepestLeaves2(root1), expected1));
        	
        	TreeNode root2 = BinaryTree.integers2BinaryTree(1);
        	TreeNode expected2 = BinaryTree.integers2BinaryTree(1);
        	assertTrue(BinaryTree.equals(lObj.lcaDeepestLeaves2(root2), expected2));
        	
        	TreeNode root3 = BinaryTree.integers2BinaryTree(0,1,3,null,2);
        	TreeNode expected3 = BinaryTree.integers2BinaryTree(2);
        	assertTrue(BinaryTree.equals(lObj.lcaDeepestLeaves2(root3), expected3));
        	
        }
    }

[https_leetcode.com_problems_lowest-common-ancestor-of-deepest-leaves]: https://leetcode.com/problems/lowest-common-ancestor-of-deepest-leaves/
[https_leetcode.com_problems_smallest-subtree-with-all-the-deepest-nodes]: https://leetcode.com/problems/smallest-subtree-with-all-the-deepest-nodes/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE4NjMwMjQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20221005/0f2ef7e32aaf4af1b0cd26693433a14b.png
[LeetCode - Medium - 236. Lowest Common Ancestor of a Binary Tree]: https://blog.csdn.net/u011863024/article/details/118059818