[leetcode]Same Tree

簡単な問題、木の再帰.

/**

 * Definition for binary tree

 * public class TreeNode {

 *     int val;

 *     TreeNode left;

 *     TreeNode right;

 *     TreeNode(int x) { val = x; }

 * }

 */

public class Solution {

    public boolean isSameTree(TreeNode p, TreeNode q) {

        // Start typing your Java solution below

        // DO NOT write main() function

        if (p == null && q == null) return true;

        if (p != null && q != null) {

            if (p.val == q.val &&

                isSameTree(p.left, q.left) &&

                isSameTree(p.right, q.right))

                return true;                

        }

        

        return false;

    }

}

再帰版ではなく、Queueを使用しており、BFSに似ています.ちなみにJavaの中のQueueは使いにくく、empty()もないのでLinkedList(Queueに引き継ぐ)を使います
参照:http://blog.csdn.net/sunbaigui/article/details/8981275

public class Solution {

    public boolean isSameTree(TreeNode p, TreeNode q) {

        // Start typing your Java solution below

        // DO NOT write main() function

        LinkedList<TreeNode> left = new LinkedList<TreeNode>();

        LinkedList<TreeNode> right = new LinkedList<TreeNode>();

        

        left.offer(p);

        right.offer(q);

        

        while (left.size() != 0 && right.size() != 0) {

            TreeNode ln = left.poll();

            TreeNode rn = right.poll();

            if (ln == null && rn == null) continue;

            if (ln == null || rn == null) return false;

            if (ln.val != rn.val) return false;

            

            left.offer(ln.left); left.offer(ln.right);

            right.offer(rn.left); right.offer(rn.right);

        }

        

        if (left.size() != 0 || right.size() != 0) return false;

        return true;

    }

}