判断二叉树是不是对称的,实现和思路分享

KLQ 2020-04-14 11:04:28 java常见问答 4679

二叉树我们应该都很熟悉,那么通常来说,怎样才能判断二叉树是否对称呢?下面一起来了解一下具体的代码实现和思路。

题目:

实现一个函数,判断一颗二叉树是否对称。

注:假如,一个二叉树同此二叉树的镜像是相同的,则定义为对称。

思路1:

递归做

代码实现:

class Solution
{
    public:
        bool isSame(TreeNode * p1, TreeNode * p2)
        {
            if (p1 == NULL && p2 != NULL) return false;
            if (p2 == NULL && p1 != NULL) return false;
            if (p1 == NULL && p2 == NULL) return true;
            if (p1 - > val == p2 - > val) return isSame(p1 - > right, p2 - > left) &&
                isSame(p1 - > left, p2 - > right);
            else
                return false;
        }
    bool isSymmetrical(TreeNode * pRoot)
    {
        if (pRoot == NULL) return true;
        return isSame(pRoot - > left, pRoot - > right);
    }
};

以上的这种方式,非常的易懂,可以参考参考。

思路2:(精简的代码)

代码实现:

class Solution
{
    public:
        bool isSymmetrical(TreeNode * pRoot)
        {
            return aux(pRoot, pRoot);
        }
    bool aux(TreeNode * l, TreeNode * r)
    {
        if (l && r && l - > val == r - > val)
            return aux(l - > left, r - > right) && aux(l - > right, r - > left);
        return !l && !r;
    }
};

思路3:

超简单java递归版本

代码实现:

public class Solution
{
    boolean isSymmetrical(TreeNode pRoot)
    {
        return is(pRoot, pRoot);
    }
    boolean is(TreeNode t1, TreeNode t2)
    {
        if (t1 == null && t2 == null)
        {
            return true;
        }
        if (t1 == null || t2 == null)
        {
            return false;
        }
        if (t1.val == t2.val)
        {
            return is(t1.left, t2.right) && is(t1.right, t2.left);
        }
        else return false;
    }
}

以上的3种实现方式思路大家都可以参考一下,当然实现方法远远不止这3种,更多的相关Java实例,请继续来本站了解吧。