【LeetCode】Same Tree解題レポート

Same Tree
[LeetCode]
https://leetcode.com/problems/same-tree/
Total Accepted: 126017 Total Submissions: 291619 Difficulty: Easy
Question
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.
Ways
この問題は木の問題で、最も基本的な木が遍歴している問題に属しています.
問題の要求は、2つのツリーが同じかどうかを判断することであり、先序に基づいて、中序または後序の遍歴が完了することができる.遍歴順序には要求がないからだ.
ここでは主に終了条件を考慮し,2つのノードがnull,すなわち先頭であればtrueを返す.どちらかがnullの場合、1つのツリーのノードが先頭にあることを示し、もう1つのツリーのノードがまだ終了していないことを示します.すなわち、ツリーが異なるか、2つのノードが空でなく、ノード値が異なるためfalseに戻ります.最後に2つのノードの左右のサブツリーを再帰処理し,左右のサブツリーの再帰と結果を返す.
ここではシーケンスループを用い,アルゴリズムの複雑さはループと一致し,再帰を用いると時間複雑度はO(n),空間複雑度はO(logn)である.コードは次のとおりです.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p==null && q==null){
            return true;
        }
        if(p==null || q==null){//    p/q             ，         
            return false;
        }
        if(p.val!=q.val){//        False，                
            return false;
        }
        return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
    }
}

AC:0ms
再帰問題は最終的に終了条件が必要です!!!必ず万全を期す.
Date
2016/4/30 1:17:33