Leetcode discuss: 1261. Find Elements in a Contaminated Binary Tree

 Here is the link. 

C# Using HashSet<int> to get O(1) time complexity to lookup

August 31, 2020
1261. Find Elements in a Contaminated Binary Tree

It is easy for me to think about using HashSet to store all node's values in the tree. So it is easy to write API Find(int target) using O(1) time complexity.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class FindElements {

    private HashSet<int> nodes = new HashSet<int>(); 

            public FindElements(TreeNode root)
            {
                nodes.Clear();
                if (root.val == 0)
                {
                    return; 
                }

                preorderTraversal(root, 0);
            }

            private void preorderTraversal(TreeNode root, int value)
            {
                if (root == null)
                {
                    return;
                }

                nodes.Add(value);
                preorderTraversal(root.left,  value * 2 + 1);
                preorderTraversal(root.right, value * 2 + 2);
            }

            public bool Find(int target)
            {
                return nodes.Contains(target);
            }
}

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