php 解法, 执行用时: 102 ms, 内存消耗: 24.5 MB, 提交时间: 2024-03-12 14:19:27

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     public $val = null;
 *     public $left = null;
 *     public $right = null;
 *     function __construct($val = 0, $left = null, $right = null) {
 *         $this->val = $val;
 *         $this->left = $left;
 *         $this->right = $right;
 *     }
 * }
 */
class FindElements {
    /**
     * @param TreeNode $root
     */
    function __construct($root) {
        $this->ans = [];
        $this->root = $root;
        if ( $root ) {
            $this->root->val = 0;
            $this->ans[] = 0;
            $this->dfs($this->root);
        }
    }
    
    function dfs($node) {
        if ( $node == null )
            return;
        
        if ( $node->left ) {
            $node->left->val = 2 * $node->val + 1;
            $this->ans[] = $node->left->val;
            $this->dfs($node->left);
        }
        
        if ( $node->right ) {
            $node->right->val = 2 * $node->val + 2;
            $this->ans[] = $node->right->val;
            $this->dfs($node->right);
        }
    }

    /**
     * @param Integer $target
     * @return Boolean
     */
    function find($target) {
        return in_array($target, $this->ans);
    }
}

/**
 * Your FindElements object will be instantiated and called as such:
 * $obj = FindElements($root);
 * $ret_1 = $obj->find($target);
 */

golang 解法, 执行用时: 24 ms, 内存消耗: 7.4 MB, 提交时间: 2022-11-17 11:17:20

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
type FindElements struct {
	aset map[int]struct{}
}

func Constructor(root *TreeNode) FindElements {
	aset := make(map[int]struct{})
	var dfs func(node *TreeNode, val int)
	dfs = func(node *TreeNode, val int) {
		if node != nil {
			node.Val = val
			aset[val] = struct{}{}
			dfs(node.Left, val*2+1)
			dfs(node.Right, val*2+2)
		}
	}
	dfs(root, 0)
	return FindElements{
		aset: aset,
	}
}

func (this *FindElements) Find(target int) bool {
	_, ok := this.aset[target]
	return ok
}


/**
 * Your FindElements object will be instantiated and called as such:
 * obj := Constructor(root);
 * param_1 := obj.Find(target);
 */

python3 解法, 执行用时: 676 ms, 内存消耗: 18.9 MB, 提交时间: 2022-11-17 11:15:01

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class FindElements:

    def __init__(self, root: Optional[TreeNode]):
        self.ans = []
        self.root = root
        if root:
            self.root.val = 0
            self.ans.append(0)
            self.dfs(self.root)
        
        
    def dfs(self, node: TreeNode):
        if not node:
            return
        
        if node.left:
            node.left.val = 2 * node.val + 1
            self.ans.append(node.left.val)
            self.dfs(node.left)
        
        if node.right:
            node.right.val = 2 * node.val + 2
            self.ans.append(node.right.val)
            self.dfs(node.right)
        


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


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

python3 解法, 执行用时: 792 ms, 内存消耗: 18.9 MB, 提交时间: 2022-11-17 11:03:09

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class FindElements:

    def __init__(self, root: Optional[TreeNode]):
        def fill(root, key):
            if not root:
                return
            else:
                root.val = key
                fill(root.left, 2*key + 1)
                fill(root.right, 2*key + 2)
        fill(root, 0)
        
        self.ans = []
        
        def inorder(root):
            if not root:
                return 
            else:
                inorder(root.left)
                self.ans.append(root.val)
                inorder(root.right)
        inorder(root)
        


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


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