美文网首页
662. Maximum Width of Binary Tre

662. Maximum Width of Binary Tre

作者: jluemmmm | 来源:发表于2021-11-22 19:55 被阅读0次

    二叉树的宽度

    层序遍历,超时了。

    /**
     * Definition for a binary tree node.
     * function TreeNode(val, left, right) {
     *     this.val = (val===undefined ? 0 : val)
     *     this.left = (left===undefined ? null : left)
     *     this.right = (right===undefined ? null : right)
     * }
     */
    /**
     * @param {TreeNode} root
     * @return {number}
     */
    var widthOfBinaryTree = function(root) {
      if (!root) return 0;
      let max = 0;
      const queue = [root];
      
      while(queue.length) {
        let n = queue.length;
        max = Math.max(max, n); 
        
        for(let i = 0; i < n; i++) {
          const node = queue.shift();
          queue.push(node ? node.left : null);
          queue.push(node ? node.right : null);
        }
        while(queue.length && !queue[queue.length - 1]) queue.pop();
        while(queue.length && !queue[0]) queue.shift();
        
      }
      return max;
    };
    
    

    由于题目约束,答案在32位有符号整数的表示范围内。js用这些方法的时候会越界,可以采用办法剪枝,保证pos不越界。

    剪枝方法:当当前层数只有一层的时候,pos重置到0

    
    var widthOfBinaryTree = function(root) {
      if (!root) return 0;
      const queue = [[root, 0]];
      let width = 0;
      while (queue.length) {
        const len = queue.length;
        if (len === 1) {
          queue[0][1] = 0;
        }
        let left = Infinity;
        let right = -Infinity;
        for (let i = 0; i < len; i++) {
          const [node, index] = queue.shift();
          left = Math.min(index, left);
          right = Math.max(index, right);
          
          if (node.left) {
            queue.push([node.left, 2 * index]);
          }
          if (node.right) {
            queue.push([node.right, 2 * index + 1]);
          }
        }
        width = Math.max(width, right - left + 1);
      }
      return width;
    };
    
    • Runtime: 142 ms, faster than 12.26%
    • Memory Usage: 43.1 MB, less than 94.19%
    /**
     * Definition for a binary tree node.
     * function TreeNode(val, left, right) {
     *     this.val = (val===undefined ? 0 : val)
     *     this.left = (left===undefined ? null : left)
     *     this.right = (right===undefined ? null : right)
     * }
     */
    /**
     * @param {TreeNode} root
     * @return {number}
     */
    var widthOfBinaryTree = function(root) {
      if (!root) return 0;
      const queue = [[root, 0]];
      let width = 0;
      while (queue.length) {
        const len = queue.length;
        if (len === 1) {
          queue[0][1] = 0;
        }
        let left = Infinity;
        let right = -Infinity;
        for (let i = 0; i < len; i++) {
          const [node, index] = queue.shift();
          left = Math.min(index, left);
          right = Math.max(index, right);
          
          if (node.left) {
            queue.push([node.left, 2 * index]);
          }
          if (node.right) {
            queue.push([node.right, 2 * index + 1]);
          }
        }
        width = Math.max(width, right - left + 1);
      }
      return width;
    };
    

    相关文章

      网友评论

          本文标题:662. Maximum Width of Binary Tre

          本文链接:https://www.haomeiwen.com/subject/wckbtrtx.html