【LeetCode】865. Smallest Subtree with all the Deepest Nodes

怼烎@ 2022-05-17 01:40 97阅读 0赞

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

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

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

Return the node with the largest depth such that it contains all the deepest nodes in its subtree.\\

Input: [3,5,1,6,2,0,8,null,null,7,4]
    Output: [2,7,4]
    Explanation:

![sketch1.png][]

We return the node with value 2, colored in yellow in the diagram.
    The nodes colored in blue are the deepest nodes of the tree.
    The input "[3, 5, 1, 6, 2, 0, 8, null, null, 7, 4]" is a serialization of the given tree.
    The output "[2, 7, 4]" is a serialization of the subtree rooted at the node with value 2.
    Both the input and output have TreeNode type.

> 解析：求二叉树最深节点所在的最小子树，如果是求深的那个叶子节点的父节点。
> 
> 解题思路：我们直接采用二分法，分别计算左右子节点的深度，该节点一定存在深度深的那一边，然后我们直接截取其中一边进行迭代循环，只至找到最小的节点。在迭代的过程中我们需要的是深度最深的父节点，所以我们需要保存的是父节点而不是其子节点。这点需要主要。

### 迭代：  ###

public TreeNode subtreeWithAllDeepest(TreeNode root) {
    		 while (root != null){
    	            int l = getDepth(root.left);
    	            int r = getDepth(root.right);
    	            if(l == r) return root;
    	            else if (l > r) root = root.left;
    	            else root= root.right;
            }
    		return root;
        }
    	 
    	 int getDepth(TreeNode root){
    	        if (root == null) return 0;
    	        int l = getDepth(root.left);
    	        int r = getDepth(root.right);
    	        return l > r ? l + 1 : r + 1;
        }

### 递归：  ###

class Solution {
        int max = 0;
    	TreeNode ret = null;
        public TreeNode subtreeWithAllDeepest(TreeNode root) {
             dfs(root,0);
    		 return ret;
        }
        private int dfs(TreeNode node , int level) {
    		 if(node == null) return level;
    		 int left = dfs(node.left,level+1);
    		 int right = dfs(node.right,level+1);
    		 if(left == right && left >= max) {
    			 ret = node;
    			 max = left;
    		 }
    		 return Math.max(left, right);
    	 }
    }

循环：

[sketch1.png]: /images/20220517/05d4ec11b27142fc9dcc264885d01fe1.png