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

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

Example 1:

Input:     1         1

          / \       / \

         2   3     2   3

        [1,2,3],   [1,2,3]

Output: true

Example 2:

Input:     1         1

          /           \

         2             2

        [1,2],     [1,null,2]

Output: false

Example 3:

Input:     1         1

          / \       / \

         2   1     1   2

        [1,2,1],   [1,1,2]

Output: false

给2个二叉树，写一个函数来判断它们是否是相同的。

解法：递归。当前节点相等，且他们左子树和右子树都相等，要考虑到树为Null的情况。基于先序，中序或者后序遍历都可以做完成，因为对遍历顺序没有要求。这里主要考虑一下结束条件，如果两个结点都是null，也就是到头了，那么返回true。如果其中一个是null，说明在一棵树上结点到头，另一棵树结点还没结束，即树不相同，或者两个结点都非空，并且结点值不相同，返回false。最后递归处理两个结点的左右子树，返回左右子树递归的与结果即可。这里使用的是先序遍历，算法的复杂度跟遍历是一致的，如果使用递归，时间复杂度是O(n)，空间复杂度是O(logn)。

Java:

class Solution {

    public boolean isSameTree(TreeNode p, TreeNode q) {

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

            return true;

        if(p==null || q==null)

            return false;

        if(p.val!=q.val)

            return false;

        return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);

    }

}

Python:

class TreeNode:

    def __init__(self, x):

        self.val = x

        self.left = None

        self.right = None

class Solution:

    # @param p, a tree node

    # @param q, a tree node

    # @return a boolean

    def isSameTree(self, p, q):

        if p is None and q is None:

            return True

        if p is not None and q is not None:

            return p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

        return False

C++：

class Solution {

    bool check(TreeNode* p, TreeNode* q) {

        // 若两个指针均为空

        if (!p && !q) return true;

        // 若只有一个指针为空

        if (!p || !q) return false;

        // 两个指针都不为空，则比较值

        if (p -> val != q -> val) return false;

        // 递归比较子节点

        return check(p -> left, q -> left) && check(p -> right, q -> right);

    }

public:

    bool isSameTree(TreeNode* p, TreeNode* q) {

        return check(p, q);

    }

};

类似题目：

[LeetCode] 110. Balanced Binary Tree 平衡二叉树

All LeetCode Questions List 题目汇总

巴特西

[LeetCode] 100. Same Tree 相同树

All LeetCode Questions List 题目汇总

最新文章

热门文章