1261.find-elements-in-a-contaminated-binary-tree.md

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

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  是否存在于还原后的二叉树中并返回结果。

来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/find-elements-in-a-contaminated-binary-tree 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

---

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 */
var FindElements = function (root) {
  function dfs(root) {
    if (root == null) return;
    if (root.left) {
      root.left.val = root.val * 2 + 1;
      dfs(root.left);
    }
    if (root.right) {
      root.right.val = root.val * 2 + 2;
      dfs(root.right);
    }
  }
  if (root != null) root.val = 0;
  dfs(root);
  this.root = root;
};

/**
 * @param {number} target
 * @return {boolean}
 */
FindElements.prototype.find = function (target) {
  let router = [],
    copy = target;
  while (copy > 0) {
    let tmp = parseInt((copy - 1) / 2);
    router.unshift(copy - 2 * tmp);
    copy = tmp;
  }
  let cur = this.root;
  for (let i = 0; i < router.length; i++) {
    if (router[i] == 1) {
      cur = cur.left;
    } else {
      cur = cur.right;
    }
    if (!cur) return false;
  }

  return true;
};