python3 解法, 执行用时: 776 ms, 内存消耗: 72 MB, 提交时间: 2023-10-08 23:43:30

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def getNumber(self, root: Optional[TreeNode], ops: List[List[int]]) -> int:
        def dfs(node):
            if node:
                yield from dfs(node.left)
                yield node.val
                yield from dfs(node.right)

        ans = 0        
        nums = [num for num in dfs(root)]
        for tp, x, y in ops[::-1]:
            ix, iy = bisect_left(nums, x), bisect_right(nums, y) - 1
            if ix <= iy:
                if tp:
                    ans += iy - ix + 1
                nums = nums[:ix] + nums[iy + 1:]
        return ans

golang 解法, 执行用时: 480 ms, 内存消耗: 30.3 MB, 提交时间: 2023-10-08 23:43:10

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func getNumber(root *TreeNode, ops [][]int) (ans int) {
    nums := []int{}

    var dfs func(node *TreeNode)
    dfs = func(node * TreeNode) {
        if node != nil {
            dfs(node.Left)
            nums = append(nums, node.Val)
            dfs(node.Right)
        }
    }

    dfs(root)
    for i := len(ops) - 1; i >= 0; i-- {
        ix, iy := bisectLeft(nums, ops[i][1]), bisectRight(nums, ops[i][2]) - 1
        if ix <= iy {
            if ops[i][0] == 1 {
                ans += iy - ix + 1
            }
            tmp := nums[iy + 1:]
            nums = nums[:ix]
            nums = append(nums, tmp...)
        }
    }
    return
}

func bisectLeft(nums []int, target int) int {
    l, r := 0, len(nums)
    for l < r {
        mid := (l + r) >> 1
        if nums[mid] >= target {
            r = mid
        } else {
            l = mid + 1
        }
    }
    return l
}

func bisectRight(nums []int, target int) int {
    l, r := 0, len(nums)
    for l < r {
        mid := (l + r) >> 1
        if nums[mid] > target {
            r = mid
        } else {
            l = mid + 1
        }
    }
    return l
}

golang 解法, 执行用时: 572 ms, 内存消耗: 21.3 MB, 提交时间: 2023-10-08 23:42:45

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func getNumber(root *TreeNode, ops [][]int) int {
	ans := 0
	n := len(ops)
	var dfs func(root *TreeNode)
	dfs = func(root *TreeNode) {
		if root == nil {
			return
		}
        for i := n - 1; i >= 0; i-- {
			if root.Val >= ops[i][1] && root.Val <= ops[i][2] {
                // fmt.Println(root.Val)
				ans += ops[i][0]
				break
			}
		}
		dfs(root.Left)
		dfs(root.Right)
	}
	dfs(root)
	return ans
}

python3 解法, 执行用时: 688 ms, 内存消耗: 72.1 MB, 提交时间: 2023-10-08 23:42:17

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def getNumber(self, root: Optional[TreeNode], ops: List[List[int]]) -> int:
        def getnext(p: Optional[TreeNode]):
            if not p:  return []
            return getnext(p.left) + [p.val] + getnext(p.right)
        
        nums = getnext(root)
        ans = 0
        for op in ops[::-1]:
            l = bisect.bisect_left(nums,op[1])
            r = bisect.bisect(nums,op[2]) - 1
            if l > r: continue 
            if op[0]==1:   ans += r - l + 1
            nums[l:r+1] = []
        return ans

javascript 解法, 执行用时: 392 ms, 内存消耗: 103.5 MB, 提交时间: 2023-10-08 23:41:08

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number[][]} ops
 * @return {number}
 */
var getNumber = function(root, ops) {
    // 从最后的操作往前冲，遇到红色的直接加1并结束，遇到蓝色的直接结束
    // 想象成坐标轴，最后的操作在最下面，往上冲，遇到的第一个颜色如果是红色+1，蓝色结束。
    const check = (node) => {
        for (let i = ops.length - 1; i >= 0; i--) {
            if (ops[i][0] === 1 && node >= ops[i][1] && node <= ops[i][2]) {
                ans++; // 遇到红色，加1结束
                break;
            }
            if (ops[i][0] === 0 && node >= ops[i][1] && node <= ops[i][2]) {
                break; // 遇到蓝色，失败结束
            }
        }
    }
    const dfs = (root) => {
        if (!root) return;
        dfs(root.left);
        check(root.val);
        dfs(root.right);
    }
    let ans = 0;
    dfs(root);
    return ans;
};

cpp 解法, 执行用时: 888 ms, 内存消耗: 292.9 MB, 提交时间: 2023-10-08 23:40:50

/**
 * 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 {
    set<int> st;

    void dfs(TreeNode *node) {
        if (node == nullptr) return;
        st.insert(node->val);
        dfs(node->left);
        dfs(node->right);
    }

public:
    int getNumber(TreeNode* root, vector<vector<int>>& ops) {
        dfs(root);
        int ans = 0;
        for (int i = (int) ops.size() - 1; i >= 0; i--) {
            while (true) {
                auto it = st.lower_bound(ops[i][1]);
                if (it == st.end() || (*it) > ops[i][2]) break;
                st.erase(it);
                if (ops[i][0]) ans++;
            }
        }
        return ans;
    }
};