Does anyone know the symbol “#” means and how dose the OJ build a Binary Tree?


  • 1
    P

    I tested my code in local,it comes out the right answer,but it can't run on the OJ,any help will be appreciated

    public int maxDepth(TreeNode root) {
    	int left=0;
    	int right=0;
    	if(root==null) return 0;
    	if(root.val==0)root.val=1;
    	if(root.left!=null){
    	    root.left.val=root.val+1;
    		left=maxDepth(root.left);
    	}
    	if(root.right!=null){
    		root.right.val=root.val+1;
    		right=maxDepth(root.right);
    	}
    	if(right!=0||left!=0){
    		if(right>=left)return right;
    		else return left;
    	}
    	return root.val;		
    }
    

    the OJ says that when input is {3,9,15,3,#,#,9,7} the expected answer is 3,but my code runs to get 5


  • 0
    M

    If you don't know why you're wrong, then you shouldn't have closed the question.

    You do realize you are destroying almost all the information in the tree aside from structure as a side effect of this function, right?

    On that note, you are getting the wrong answer because you assume the root.val is 0 or 1 for the true root. With the input provided, the root.val = 3, and then you assign root.val+1 (4) to both children, and then child.val+1(5) to the grandchildren. The grandchildren then return that value back up the chain to give you your answer. If root.val were 0 or 1, it would change 0 to 1, change child.val to 1+1=2, and then change gchild.val to 2+1=3, technically giving the correct answer.

    While incredibly evil code with its side effect, it will work if the true root.val is 0 or 1, and fail in all other cases.

    As for your title question, the printed trees use a modified level-order traversal described on several tree problems under the "confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ." link. The # means end of line of descent, not just "This is a null element," but is otherwise a level-order traversal.


  • 0
    P

    thanks very much,your answer make me impressive,it helps me solved this problem


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.