LeetCode - Medium - 1261. Find Elements in a Contaminated Binary Tree

红太狼 2022-10-13 12:52 134阅读 0赞

## Topic ##

*  Tree
 *  Depth-First Search
 *  Breadth-First Search
 *  Design
 *  Binary Tree

## Description ##

[https://leetcode.com/problems/find-elements-in-a-contaminated-binary-tree/][https_leetcode.com_problems_find-elements-in-a-contaminated-binary-tree]

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:**

![707a7ebab3278cc4d114c53865942d7a.png][]

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

**Example 2:**

![4d40eadebe805d351652790f9e9d72df.png][]

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

**Example 3:**

![334d9d856c9b9b62b0baf18c99860bc1.png][]

Input
    ["FindElements","find","find","find","find"]
    [[[-1,null,-1,-1,null,-1]],[2],[3],[4],[5]]
    Output
    [null,true,false,false,true]
    Explanation
    FindElements findElements = new FindElements([-1,null,-1,-1,null,-1]);
    findElements.find(2); // return True
    findElements.find(3); // return False
    findElements.find(4); // return False
    findElements.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 , 1 0 4 \] \[1, 10^4\] \[1,104\]
 *  Total calls of `find()` is between  \[ 1 , 1 0 4 \] \[1, 10^4\] \[1,104\]
 *   0 < = t a r g e t < = 1 0 6 0 <= target <= 10^6 0<=target<=106

## Analysis ##

![在这里插入图片描述][20210707105505890.png_pic_center]

## Submission ##

import com.lun.util.BinaryTree.TreeNode;
    
    public class FindElementsInAContaminatedBinaryTree { 
    	public static class FindElements { 
    
    		private TreeNode root;
    		
    	    public FindElements(TreeNode root) { 
    	        this.root = root;
    	    }
    	    
    	    public boolean find(int target) { 
    	    	TreeNode p = root;
    	    	target++;
    	    	
    	    	int temp = 0;
    	    	//指向target最左二数位
    	    	for(int i = 1; (target >> i) > 0; i++)
    	    		temp = temp == 0 ? 1 : temp << 1;
    	    	
    	    	while(temp > 0) { 
    	    		boolean left = (target & temp) == 0;
    	    		
    	    		if(p.left == null && left || p.right == null && !left)
    	    			return false;
    	    		
    	    		p = left ? p.left : p.right;
    	    		temp >>>= 1;
    	    	}
    	        return true;
    	    }	    
    	}
    }

## Test ##

import static org.junit.Assert.*;
    import org.junit.Test;
    
    import com.lun.medium.FindElementsInAContaminatedBinaryTree.FindElements;
    import com.lun.util.BinaryTree;
    import com.lun.util.BinaryTree.TreeNode;
    
    public class FindElementsInAContaminatedBinaryTreeTest { 
    
        @Test
        public void test() { 
            FindElementsInAContaminatedBinaryTree fObj = new FindElementsInAContaminatedBinaryTree();
            FindElements f1 = new FindElements(BinaryTree.of(-1,null,-1));
            assertTrue(f1.find(0));
            assertFalse(f1.find(1));
            assertTrue(f1.find(2));
    
            FindElements f2 = new FindElements(BinaryTree.of(-1,-1,-1,-1,-1));
            assertTrue(f2.find(1));
            assertTrue(f2.find(3));
            assertFalse(f2.find(5));
            
            FindElements f3 = new FindElements(BinaryTree.of(-1,null,-1,-1,null,-1));
            assertTrue(f3.find(2));
            assertFalse(f3.find(3));
            assertFalse(f3.find(4));
            assertTrue(f3.find(5));
            
        }
    }

[https_leetcode.com_problems_find-elements-in-a-contaminated-binary-tree]: https://leetcode.com/problems/find-elements-in-a-contaminated-binary-tree/
[707a7ebab3278cc4d114c53865942d7a.png]: /images/20221005/cbd7f8dff6aa4cc0927595481cd9e3b3.png
[4d40eadebe805d351652790f9e9d72df.png]: /images/20221005/d9c07f4aa6984b7ba9e0046f47869893.png
[334d9d856c9b9b62b0baf18c99860bc1.png]: /images/20221005/84044812977c4134b08a6c0c583887e4.png
[20210707105505890.png_pic_center]: /images/20221005/8ae65ce14dd34ceaa3f7494eccbdf048.png