首页 > 其他 > 详细

[LeetCode#100]Same Tree

时间:2015-01-11 06:06:59      阅读:247      评论:0      收藏:0      [点我收藏+]

The problem:

Given two binary trees, write a function to check if they are equal or not.

Two binary trees are considered equal if they are structurally identical and the nodes have the same value.

 

My analysis:

This problem is very easy, and we can conclude some common routines in writing a recursion program.
1. Usually, we need future information(information from post recursion level) to make decision
return helper(cur_root1.left, cur_root2.left) && helper(cur_root1.right, cur_root2.right);
Thus, until we reach the base case, we won‘t return "true" value.

if (cur_root1 == null && cur_root2 == null) //also take care of the illegal base case!!!
    return true;

 

2. During the recursion level that is not he base level, we won‘t return "true" value based on current level‘s judgement. But we can return "false" value to indicate the violation happens in the current level, we no longer need to go on the searching!
Note:this idea is very classic in constraining the searching space.

if (cur_root1.val != cur_root2.val) 
    return false;

 

My solution:

public class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        
        return helper(p, q);
    }
    
    private boolean helper(TreeNode cur_root1, TreeNode cur_root2) {
        
        if (cur_root1 == null && cur_root2 == null) //both two roots are null, only base case or violation can directly return
            return true;
        
        if (cur_root1 == null || cur_root2 == null) //only one root is null
            return false; 
        
        if (cur_root1.val != cur_root2.val) 
            return false; 
            
        return  helper(cur_root1.left, cur_root2.left) && helper(cur_root1.right, cur_root2.right);
    }
}

 

[LeetCode#100]Same Tree

原文:http://www.cnblogs.com/airwindow/p/4216036.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!