LeetCode 二叉树最大深度（递归）

给定一个二叉树，编写一个函数来获取这个树的最大宽度。树的宽度是所有层中的最大宽度。这个二叉树与满二叉树（full binary tree）结构相同，但一些节点为空。

每一层的宽度被定义为两个端点（该层最左和最右的非空节点，两端点间的null节点也计入长度）之间的长度。
示例 1:

输入: 
           1
         /   \
        3     2
       / \     \  
      5   3     9 
输出: 4
解释: 最大值出现在树的第 3 层，宽度为 4 (5,3,null,9)。

示例 2:

输入: 
          1
         /  
        3    
       / \       
      5   3     
输出: 2
解释: 最大值出现在树的第 3 层，宽度为 2 (5,3)。

示例 3:

输入: 
          1
         / \
        3   2 
       /        
      5      

输出: 2
解释: 最大值出现在树的第 2 层，宽度为 2 (3,2)。

示例 4:

输入: 
          1
         / \
        3   2
       /     \  
      5       9 
     /         \
    6           7
输出: 8
解释: 最大值出现在树的第 4 层，宽度为 8 (6,null,null,null,null,null,null,7)。

注意: 答案在32位有符号整数的表示范围内。
思路分析： 如果我们从根节点开始标号为1，则根节点与左右子节点存在一个规律，leftIndex = rootIndex * 2，rightIndex = rootIndex * 2 + 1。所以我们只要记录每一层的第一个下标，然后动态更新最大值即可。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    unsigned long long maxRes = 1;
    unordered_map<int, int> hashMap;//hashMap[deep]用于记录deep层第一个节点的下标
    int widthOfBinaryTree(TreeNode* root) {
        dfs(root, 1, 1);
        return maxRes;
    }
    //deepth代表root的深度，rootIndex代表的是root的深度
    void dfs(TreeNode* root, int deepth, unsigned long long rootIndex){
        if (root == NULL){
            return;
        }
        if (root->left){
            dfs(root->left, deepth + 1, rootIndex * 2);
        }
        if (hashMap.count(deepth)){
            //如果root不是此层访问的第一个节点，则更新最大宽度
            maxRes = max(maxRes, rootIndex - hashMap[deepth] + 1);
        }
        else{
            //否则此层第一个节点，需要标记下标
            hashMap[deepth] = rootIndex;
        }
        if (root->right){
            dfs(root->right, deepth + 1, rootIndex * 2 + 1);
        }
    }
};

LeetCode 二叉树最大深度（递归）
有几个测试数据非常变态，二叉树的深度非常大，导致下标溢出。。。

LeetCode 二叉树最大深度（递归）

相关推荐