Lstmxx的空间

1261. 在受污染的二叉树中查找元素

给出一个满足下述规则的二叉树：

• root.val == 0
• 如果 treeNode.val == x 且 treeNode.left != null，那么 treeNode.left.val == 2 * x + 1
• 如果 treeNode.val == x 且 treeNode.right != null，那么 treeNode.right.val == 2 * x + 2

现在这个二叉树受到「污染」，所有的 treeNode.val 都变成了 -1。

请你先还原二叉树，然后实现 FindElements 类：

• FindElements(TreeNode* root) 用受污染的二叉树初始化对象，你需要先把它还原。
• bool find(int target) 判断目标值 target 是否存在于还原后的二叉树中并返回结果。

链接

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

class FindElements {
  node: TreeNode
  constructor(root: TreeNode | null) {
    this.init(root)
    this.node = root
  }
  init(node: TreeNode) {
    if (node === null) return
    if (node.val === -1) {
      node.val = 0
    }
    if (node.left) {
      node.left.val = node.val * 2 + 1
    }
    if (node.right) {
      node.right.val = node.val * 2 + 2
    }
    this.init(node.left)
    this.init(node.right)
  }
  findDfs(node: TreeNode, target: number): boolean {
    if (node === null) return false
    const l = this.findDfs(node.left, target)
    const r = this.findDfs(node.right, target)
    return node.val === target || l || r
  }
  find(target: number): boolean {
    return this.findDfs(this.node, target)
  }
}

/**
 * Your FindElements object will be instantiated and called as such:
 * var obj = new FindElements(root)
 * var param_1 = obj.find(target)
 */