Netherspite

树

117. Populating Next Right Pointers in Each Node II

Description

Input: root = [1,2,3,4,5,null,7]
Output: [1,#,2,3,#,4,5,7,#]
Explanation: Given the above binary tree (Figure A), your function should populate each next pointer to point to its next right node, just like in Figure B. The serialized output is in level order as connected by the next pointers, with ‘#’ signifying the end of each level.

Solution

/**
 * // Definition for a Node.
 * function Node(val, left, right, next) {
 *    this.val = val === undefined ? null : val;
 *    this.left = left === undefined ? null : left;
 *    this.right = right === undefined ? null : right;
 *    this.next = next === undefined ? null : next;
 * };
 */
/**
 * @param {Node} root
 * @return {Node}
 */
var connect = function(root) {
    if(root === null) return null;
    let stack = [root];
    while(stack.length > 0) {
        let n = stack.length;
        for(let i = 0; i < n; i++) {
            stack[0].next = i === n - 1 ? null : stack[1];
            if(stack[0].left !== null) stack.push(stack[0].left);
            if(stack[0].right !== null) stack.push(stack[0].right);
            stack.shift();
        }
    }
    return root;
};

105. Construct Binary Tree from Preorder and Inorder Traversal

Description

Given preorder and inorder traversal of a tree, construct the binary tree.

Solution

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {number[]} preorder
 * @param {number[]} inorder
 * @return {TreeNode}
 */
var buildTree = function(preorder, inorder) {
    if(preorder.length === 0 || inorder.length === 0) return null;
    let root = new TreeNode(preorder.shift());
    let index = inorder.indexOf(root.val);
    root.left = buildTree(preorder, inorder.slice(0, index));
    root.right = buildTree(preorder, inorder.slice(index + 1));
    return root;
};

106. Construct Binary Tree from Inorder and Postorder Traversal

Description

Given inorder and postorder traversal of a tree, construct the binary tree.

Solution

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {number[]} inorder
 * @param {number[]} postorder
 * @return {TreeNode}
 */
var buildTree = function(inorder, postorder) {
    if(inorder.length === 0 || postorder.length === 0) return null;
    let root = new TreeNode(postorder.pop()),
        index = inorder.indexOf(root.val);
    root.right = buildTree(inorder.slice(index + 1), postorder);
    root.left = buildTree(inorder.slice(0, index), postorder);
    return root;
};

95. 96. Unique Binary Search Trees

Description

Given n, how many structurally unique BST’s (binary search trees) that store values 1 … n?

Given an integer n, generate all structurally unique BST’s (binary search trees) that store values 1 … n.

Solution

以1为根的树的个数，等于左子树的个数乘以右子树的个数，左子树是0个元素的树，右子树是2个元素的树。以2为根的树的个数，等于左子树的个数乘以右子树的个数，左子树是1个元素的树，右子树也是1个元素的树。依此类推。
当数组为1, 2, .., n时，基于以下原则的构建的BST树具有唯一性：以i为根节点的树，其左子树由[1, i-1]构成，其右子树由[i+1, n]构成。

/**
 * @param {number} n
 * @return {number}
 */
var numTrees = function(n) {
    let num = Array(n + 1).fill(0);
    num.splice(0, 4, ...[1, 1, 2, 5]);
    if(n < 4) return num[n];
    for(let i = 4; i <= n; i++) {
        for(let k = 1; k <= i; k++) {
            num[i] += num[k - 1] * num[i - k];
        }
    }
    return num[n];
};

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {number} n
 * @return {TreeNode[]}
 */
var generateTrees = function(n) {
    if(n === 0) return [];
    return trees(1, n);
};
function trees(start, end) {
    let sub = [];
    if(start > end) {
        sub.push(null);
        return sub;
    }
    for(let k = start; k <= end; k++) {
        let left = trees(start, k - 1);
        let right = trees(k + 1, end);
        for(let i of left) {
            for(let j of right) {
                let node = new TreeNode(k);
                node.left = i;
                node.right = j;
                sub.push(node);
            }
        }
    }
    return sub;
}

98. Validate Binary Search Tree

Description

Given a binary tree, determine if it is a valid binary search tree (BST). Assume a BST is defined as follows:

  • The left subtree of a node contains only nodes with keys less than the node’s key.
  • The right subtree of a node contains only nodes with keys greater than the node’s key.
  • Both the left and right subtrees must also be binary search trees.

Solution

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isValidBST = function(root) {
    function isValid(root, min, max) {
        if(!root) return true;
        return root.val > min && root.val < max &&
            isValid(root.left, min, root.val) && isValid(root.right, root.val, max);
    }
    return isValid(root, -Infinity, Infinity);
};

104. Maximum Depth of Binary Tree

Description

Given a binary tree, find its maximum depth.

Solution

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxDepth = function(root) {
    if(!root) return 0;
    let maxLeft = maxDepth(root.left),
        maxRight = maxDepth(root.right);
    return Math.max(maxLeft, maxRight) + 1;
};

572. Subtree of Another Tree

Description

Given two non-empty binary trees s and t, check whether tree t has exactly the same structure and node values with a subtree of s. A subtree of s is a tree consists of a node in s and all of this node’s descendants. The tree s could also be considered as a subtree of itself.

Solution

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} s
 * @param {TreeNode} t
 * @return {boolean}
 */
var isSubtree = function(s, t) {
    return match(s, t);
};
function subtree(s, t) {
    if(!s && !t) return true;
    if(!s || !t) return false;
    return s.val === t.val && subtree(s.left, t.left) && subtree(s.right, t.right);
}
function match(s, t) {
    return !!s && (subtree(s, t) || match(s.left, t) || match(s.right, t));
}

108. Convert Sorted Array to Binary Search Tree

Description

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

Solution

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {number[]} nums
 * @return {TreeNode}
 */
var sortedArrayToBST = function(nums) {
    return arr2bst(nums, 0, nums.length);
};
function arr2bst(nums, start, end) {
    let len = end - start;
    if(len <= 0) return null;
    let mid = Math.floor(start + len / 2);
    let root = new TreeNode(nums[mid]);
    root.left = arr2bst(nums, start, mid);
    root.right = arr2bst(nums, mid + 1, end);
    return root;
}

109. Convert Sorted List to Binary Search Tree

Description

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

Solution

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {TreeNode}
 */
//转成数组偷鸡版
var sortedListToBST = function(head) {
    let arr = [];
    while(!!head) {
        arr.push(head.val);
        head = head.next;
    }
    return list2bst(arr, 0, arr.length);
};
function list2bst(arr, start, end) {
    let m = end - start;
    if(m <= 0) return null;
    let n = Math.floor(m / 2) + start;
    let root = new TreeNode(arr[n]);
    root.left = list2bst(arr, start, n);
    root.right = list2bst(arr, n + 1, end);
    return root;
} 
//正经版
let node;
var sortedListToBST = function(head) {
    let n = 0, p = head;
    while(!!p) {
        n++;
        p = p.next;
    }
    node = head;
    return list2bst(0, n - 1);
}
function list2bst(start, end) {
    if(end < start) return null;
    let mid = Math.floor((start + end) / 2);
    let left = list2bst(start, mid - 1);
    let root = new TreeNode(node.val);
    root.left = left;
    node = node.next;
    root.right = list2bst(mid + 1, end);
    return root;
}

111. Minimum Depth of Binary Tree

Description

Given a binary tree, find its minimum depth.

Solution

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
//迭代版
var minDepth = function(root) {
    if(!root) return 0;
    let s = [root], min = 1;
    outer: while(s.length > 0) {
        for(let m = s.length; m > 0; m--) {
            if(!s[0].left && !s[0].right) break outer;
            !!s[0].left && s.push(s[0].left);
            !!s[0].right && s.push(s[0].right);
            s.shift();
        }
        if(s.length > 0) min++;
    }
    return min;
};
//递归版
var minDepth = function(root) {
  return minD(root, false);
}
function minD(root, brother) {
  if(!root) return brother ? Infinity : 0;
  return 1 + Math.min(minD(root.left, !!root.right), minD(root.right, !!root.left));
}

104. Maximum Depth of Binary Tree

Description

Given a binary tree, find its maximum depth.

Solution

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxDepth = function(root) {
    if(!root) return 0;
    let maxLeft = maxDepth(root.left),
        maxRight = maxDepth(root.right);
    return Math.max(maxLeft, maxRight) + 1;
};

112. Path Sum & 113. Path Sum II

Description

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

Solution

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} sum
 * @return {boolean}
 */
var hasPathSum = function(root, sum) {
    if(!root) return false;
    if(!root.left && !root.right) return root.val === sum;
    return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
};
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} sum
 * @return {number[][]}
 */
var pathSum = function(root, sum) {
    let result = [], temp = [];
    path(root, sum, temp, result);
    return result;
};
function path(root, sum, temp, result) {
    if(root === null) return;
    temp.push(root.val);
    if(root.left === null && root.right === null) {
         if(sum === root.val) result.push(temp.slice());
    }else {
        path(root.left, sum - root.val, temp, result);
        path(root.right, sum - root.val, temp, result);
    }
    temp.pop();
}


 上一页

CSS JavaScript

 评论