2022-08-05

[Zheaoli]

2022-08-05

[SaraadKun]

623. 在二叉树中增加一行

class Solution {
    public TreeNode addOneRow(TreeNode root, int val, int depth) {
        if (root == null) {
            return null;
        }
        if (depth == 1) {
            return new TreeNode(val, root, null);
        }
        if (depth == 2) {
            root.left = new TreeNode(val, root.left, null);
            root.right = new TreeNode(val, null, root.right);
        } else {
            addOneRow(root.left, val, depth - 1);
            addOneRow(root.right, val, depth - 1);
        }
        return root;
    }
}

---

WeChat: Saraad

[SaraadKun]

剑指 Offer 32 - III. 从上到下打印二叉树 III

class Solution {

    Map<Integer, List<Integer>> map = new HashMap<>();
    int maxDepth = -1;
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();
        dfs(root, 0);
        for (int i = 0; i <= maxDepth; i++) {
            if ((i & 1) == 1) {
                Collections.reverse(map.get(i));
            } 
            ans.add(map.get(i));
        }
        return ans;
    }

    private void dfs(TreeNode root, int depth) {
        if (root == null) {
            return;
        }
        List<Integer> list = map.get(depth);
        if (list == null) {
            list = new ArrayList<>();
            map.put(depth, list);    
        }
        list.add(root.val);
        maxDepth = Math.max(depth, maxDepth);
        dfs(root.left, depth + 1);
        dfs(root.right, depth + 1);
    }
}

---

WeChat: Saraad

[restartgr]

/*
 * @lc app=leetcode.cn id=617 lang=javascript
 *
 * [617] 合并二叉树
 */

// @lc code=start
/**
 * 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} root1
 * @param {TreeNode} root2
 * @return {TreeNode}
 */
var mergeTrees = function (root1, root2) {
    if (!root1) {
        return root2
    }
    if (!root2) {
        return root1
    }
    root1.val += root2.val
    root1.left = mergeTrees(root1.left, root2.left)
    root1.right = mergeTrees(root1.right, root2.right)
    return root1
};
// @lc code=end

---

微信id: Jörmungandr 来自 vscode 插件

[restartgr]

/*
 * @lc app=leetcode.cn id=700 lang=javascript
 *
 * [700] 二叉搜索树中的搜索
 */

// @lc code=start
/**
 * 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} val
 * @return {TreeNode}
 */
var searchBST = function (root, val) {
    if (!root || root.val === val) {
        return root
    }
    if (root.val > val) {
        return searchBST(root.left, val)
    }
    if (root.val < val) {
        return searchBST(root.right, val)
    }
    return null
};
// @lc code=end

---

微信id: Jörmungandr 来自 vscode 插件

[restartgr]

/*
 * @lc app=leetcode.cn id=98 lang=javascript
 *
 * [98] 验证二叉搜索树
 */

// @lc code=start
/**
 * 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 {boolean}
 */
var isValidBST = function (root) {
    const res = []
    const traverse = (root) => {
        if (!root) {
            return null
        }
        traverse(root.left)
        res.push(root.val)
        traverse(root.right)
    }
    traverse(root)
    for (let i = 0; i + 1 < res.length; i++) {
        if (res[i] >= res[i + 1]) {
            return false
        }
    }
    return true
};
// @lc code=end

---

微信id: Jörmungandr 来自 vscode 插件

[restartgr]

/*
 * @lc app=leetcode.cn id=530 lang=javascript
 *
 * [530] 二叉搜索树的最小绝对差
 */

// @lc code=start
/**
 * 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 getMinimumDifference = function (root) {
    const res = []
    const treverse = (root) => {
        if (!root) {
            return
        }
        treverse(root.left)
        res.push(root.val)
        treverse(root.right)
    }
    treverse(root)
    let min = Infinity
    for (let i = 1; i < res.length; i++) {
        min = Math.min(min, res[i] - res[i - 1])
    }
    return min
};
// @lc code=end

---

微信id: Jörmungandr 来自 vscode 插件

[gongpeione]

/*
 * @lc app=leetcode id=70 lang=typescript
 *
 * [70] Climbing Stairs
 * DP: https://www.youtube.com/watch?v=Y0lT9Fck7qI
 * n = 5
 * stair 0 1 2 3 4 5
 * ways  8 5 3 2 1 1
 * [5] has 1 way
 * [4] has 1 way
 * [3] has [4] + [5] = 2 ways
 * [2] has [3] + [4] = 3 ways
 * [1] has [2] + [3] = 5 ways
 * [0] has [1] + [2] = 8 ways
 */

// @lc code=start
function climbStairs(n: number): number {
    let one = 1;
    let two = 1;

    for (let i = 0; i < n - 1; i++) {
        [one, two] = [one + two, one];
    }

    return one;
};
// @lc code=end

---

微信id: 弘树 来自 vscode 插件