動機

這題讓我把binary編碼與complete binary tree的關係找回來了

Problem

Given a binary tree with the following rules:

  1. root.val == 0
  2. If treeNode.val == x and treeNode.left != null, then treeNode.left.val == 2 * x + 1
  3. If treeNode.val == x and treeNode.right != null, then treeNode.right.val == 2 * x + 2

Now the binary tree is contaminated, which means all treeNode.val have been changed to -1.

Implement the FindElements class:

  • FindElements(TreeNode* root) Initializes the object with a contaminated binary tree and recovers it.
  • bool find(int target) Returns true if the target value exists in the recovered binary tree.

 

Example 1:

Input[FindElements,find,find][[[-1,null,-1]],[1],[2]]Output[null,false,true]ExplanationFindElements findElements = new FindElements([-1,null,-1]); findElements.find(1); // return False findElements.find(2); // return True

Example 2:

Input[FindElements,find,find,find][[[-1,-1,-1,-1,-1]],[1],[3],[5]]Output[null,true,true,false]ExplanationFindElements findElements = new FindElements([-1,-1,-1,-1,-1]);findElements.find(1); // return TruefindElements.find(3); // return TruefindElements.find(5); // return False

Example 3:

Input[FindElements,find,find,find,find][[[-1,null,-1,-1,null,-1]],[2],[3],[4],[5]]Output[null,true,false,false,true]ExplanationFindElements findElements = new FindElements([-1,null,-1,-1,null,-1]);findElements.find(2); // return TruefindElements.find(3); // return FalsefindElements.find(4); // return FalsefindElements.find(5); // return True

 

Constraints:

  • TreeNode.val == -1
  • The height of the binary tree is less than or equal to 20
  • The total number of nodes is between [1, 104]
  • Total calls of find() is between [1, 104]
  • 0 <= target <= 106

Sol1: DFS (TLE)

兩邊都走，當然就超時啦 明明就有數字可以決定走哪

def dfs(r,n=0):
    if r:
        r.val = n
        dfs(r.left,2*n+1)
        dfs(r.right,2*n+2)
class FindElements:
    def ff(self, target, tmp):
        if not tmp:
            return False
        elif tmp.val == target:
            return True
        else:
            return self.ff(target, tmp.left) or self.ff(target, tmp.right)
    def __init__(self, root: TreeNode):
        dfs(root)
        self.root = root

    def find(self, target: int) -> bool:
        return self.ff(target, self.root)

Sol2: Hash (AC)

都會走dfs，就把數字存到hash就好了

class FindElements:
    def ff(self,root,  acc=0):
        if root:
            self.tbl.add(acc)
            self.ff(root.left,acc*2+1)
            self.ff(root.right,acc*2+2)
    def __init__(self, root: TreeNode):
        self.tbl = set()
        self.ff(root)

    def find(self, target: int) -> bool:
        return target in self.tbl

Sol3: Binary (AC)

觀察編碼與節點的對應是 2^depth-1

所以可以先加1，轉成binary，從倒數第二個數字開始往頭走(reverse order)

像5為例

  1. 5+1 = 6
  2. 6 = 110
  3. 10 => left, right
class FindElements:
    def dfs(self, s, i, r):
        if not r:
            return False
        elif i >= len(s):
            return r is not None
        else:
            if s[i] == '0':
                return self.dfs(s,i+1,r.left)
            else:
                return self.dfs(s,i+1,r.right)
    def __init__(self, root: TreeNode):
        self.r = root

    def find(self, target: int) -> bool:
        target += 1
        s = format(target,'b')
        return self.dfs(s[1:], 0, self.r)

Ref

Binary的詳解