LeeCode-刷题日记-Day29

199. 二叉树的右视图

思路：层序遍历此树，拿到每层的最后一个节点。则此数组为右视图数组。

/**
 * 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 rightSideView = function(root) {
    let res=[];
    if(!root)
        return res;
    let queue=[];
    queue.push(root)
    while(queue.length>0){
        let a=[];
        let len=queue.length;
        for(let i=0;i<len;i++){
            let cur=queue.shift();
            a.push(cur.val);
            if(cur.left)
                queue.push(cur.left);
            if(cur.right)
                queue.push(cur.right);
        }
        res.push(a);
    }
    let m=[];
    for(let i=0;i<res.length;i++){
        m.push(res[i].pop());
    }
    return m;
};

113. 路径总和 II

思路：采用递归的思想。每次进入一个节点，判断当前节点是否为非叶节点，同时值小于Sum值。如果满足则将Sum值减掉当前节点的值。继续向下遍历。

如果当前Sum值为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
 * @param {number} targetSum
 * @return {number[][]}
 */
var pathSum = function(root, targetSum) {
    let res=[];
    let path=[];
    if(!root)
        return res;
    function getPath(root,cntSum){
        let flag=(root.val<=cntSum||Math.abs(root.val)<=Math.abs(cntSum))
        ||root.left!=null||root.right!=null;
        if(flag){
            path.push(root.val);
            cntSum-=root.val;
        }else{
            return;
        }

        if(cntSum===0&&root.left===null&&root.right===null){
            res.push(path.map(val=>val));
            path.pop();
            return;
        }
        if(root.left!==null)
            getPath(root.left,cntSum);
        if(root.right!==null)
            getPath(root.right,cntSum);
        path.pop();
    }
    getPath(root,targetSum);
    return res;
};

450. 删除二叉搜索树中的节点

思路：

首先递归查找到需要删除的节点。

节点没有左右子树时，直接删除。

有左子树时，继承左子树。

有右子树时，继承右子树。

有左右子树时，查找到右子树中最小节点。再在右子树中删除此节点。并将此节点的左右子树赋值为当前需要删除节点的左右子树即可。

/**
 * 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
 * @param {number} key
 * @return {TreeNode}
 */
var deleteNode = function(root, key) {
    if(!root)
        return null;
    if(root.val<key){
        root.right=deleteNode(root.right,key);
        return root;
    }
    if(root.val>key){
        root.left=deleteNode(root.left,key);
        return root;
    }
    if(root.val===key){
        if(root.left===null&&root.right===null)
            return null;
        if(root.left===null)
            return root.right;
        if(root.right===null)
            return root.left;
        let successor=root.right;
        while(successor.left){
            successor=successor.left;
        }
        root.right=deleteNode(root.right,successor.val);
        successor.right=root.right;
        successor.left=root.left;
        return successor;
    }
    return root;
};