LeetCode - Medium - 865. Smallest Subtree with all the Deepest Nodes

爱被打了一巴掌 2022-10-09 00:58 8阅读 0赞

## Topic ##

*  Tree
 *  Depth-first Search
 *  Breadth-first Search
 *  Recursion

## Description ##

[https://leetcode.com/problems/smallest-subtree-with-all-the-deepest-nodes/][https_leetcode.com_problems_smallest-subtree-with-all-the-deepest-nodes]

Given the `root` of a binary tree, the depth of each node is **the shortest distance to the root**.

Return the smallest subtree such that it contains `all the deepest nodes` in the original tree.

A node is called `the deepest` if it has the largest depth possible among any node in the entire tree.

The `subtree` of a node is tree consisting of that node, plus the set of all descendants of that node.

**Note:** This question is the same as 1123: [https://leetcode.com/problems/lowest-common-ancestor-of-deepest-leaves/][https_leetcode.com_problems_lowest-common-ancestor-of-deepest-leaves]

**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 nodes of the tree.
    Notice that nodes 5, 3 and 2 contain the deepest nodes in the tree but node 2 is the smallest subtree among them, so we return it.

**Example 2:**

Input: root = [1]
    Output: [1]
    Explanation: The root is the deepest node in the tree.

**Example 3:**

Input: root = [0,1,3,null,2]
    Output: [2]
    Explanation: The deepest node in the tree is 2, the valid subtrees are the subtrees of nodes 2, 1 and 0 but the subtree of node 2 is the smallest.

**Constraints:**

*  The number of nodes in the tree will be in the range  \[ 1 , 500 \] \[1, 500\] \[1,500\].
 *   0 < = N o d e . v a l < = 500 0 <= Node.val <= 500 0<=Node.val<=500
 *  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;
    import com.lun.util.Pair;
    
    public class SmallestSubtreeWithAllTheDeepestNodes { 
    	
    	//方法一：自己写的，用后序遍历模式
        public TreeNode subtreeWithAllDeepest(TreeNode root) { 
        	Object[] result = subtreeWithAllDeepest(root, 0);
        	return result != null ? (TreeNode)result[0] : null;
        }
        
        private Object[] subtreeWithAllDeepest(TreeNode node, int depth) { 
        	if(node == null) return null;
        	
        	depth++;
        	
        	Object[] leftResult = subtreeWithAllDeepest(node.left, depth);
        	Object[] rightResult = subtreeWithAllDeepest(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 subtreeWithAllDeepest2(TreeNode root) { 
            return deep(root).getSecond();
        }
    
        public Pair<Integer, TreeNode> deep(TreeNode root) { 
            if (root == null) return new Pair<>(0, null);
            Pair<Integer, TreeNode> l = deep(root.left), r = deep(root.right);
    
            int d1 = l.getFirst(), d2 = r.getFirst();
            return new Pair<>(Math.max(d1, d2) + 1, d1 == d2 ? root : d1 > d2 ? l.getSecond() : r.getSecond());
        }
        
        
    }

## Test ##

import static org.junit.Assert.*;
    import org.junit.Test;
    
    import com.lun.util.BinaryTree;
    import com.lun.util.BinaryTree.TreeNode;
    
    public class SmallestSubtreeWithAllTheDeepestNodesTest { 
    
        @Test
        public void test() { 
            SmallestSubtreeWithAllTheDeepestNodes sObj = new SmallestSubtreeWithAllTheDeepestNodes();
    
            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(sObj.subtreeWithAllDeepest(root1), expected1));
            
            TreeNode root2 = BinaryTree.integers2BinaryTree(1);
            TreeNode expected2 = BinaryTree.integers2BinaryTree(1);
            assertTrue(BinaryTree.equals(sObj.subtreeWithAllDeepest(root2), expected2));
            
            TreeNode root3 = BinaryTree.integers2BinaryTree(0,1,3,null,2);
            TreeNode expected3 = BinaryTree.integers2BinaryTree(2);
            assertTrue(BinaryTree.equals(sObj.subtreeWithAllDeepest(root3), expected3));
        }
        
        @Test
        public void test2() { 
        	SmallestSubtreeWithAllTheDeepestNodes sObj = new SmallestSubtreeWithAllTheDeepestNodes();
        	
        	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(sObj.subtreeWithAllDeepest2(root1), expected1));
        	
        	TreeNode root2 = BinaryTree.integers2BinaryTree(1);
        	TreeNode expected2 = BinaryTree.integers2BinaryTree(1);
        	assertTrue(BinaryTree.equals(sObj.subtreeWithAllDeepest2(root2), expected2));
        	
        	TreeNode root3 = BinaryTree.integers2BinaryTree(0,1,3,null,2);
        	TreeNode expected3 = BinaryTree.integers2BinaryTree(2);
        	assertTrue(BinaryTree.equals(sObj.subtreeWithAllDeepest2(root3), expected3));
        }
    }

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