LeetCode OJ Symmetric Tree 判断是否为对称树（AC代码）

思路：

主要判断左子树与右子树。

在判断左时，循环下去肯定会到达叶子结点中最左边的结点与最右边的结点比较。

到了这一步因为他们都没有左（右）子树了，所以得开始判断这两个结点的右（左）子树了。

当某个结点对称了，它的左子树也对称了，右子树也对称了，那才是真的对称了。

C++

 /**

  * Definition for binary tree

  * struct TreeNode {

  *     int val;

  *     TreeNode *left;

  *     TreeNode *right;

  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}

  * };

  */

 class Solution {

 public:

     bool isSymmetric(TreeNode *root) {

         if(!root)

             return true;    //无根结点

         else if(root->left==(void*) && root->right==(void*))        //只有根结点的树

             return true;

         else if(root->left!=(void*) && root->right!=(void*) && isSymmetric(root->left,root->right))    //两个子树非空,左右子树为对称

             return true;

         else

             return false;

     }

     bool isSymmetric(TreeNode *left,TreeNode *right) {

         if(left->val==right->val){        //左右结点值相等

             if(left->left==(void*) && right->right==(void*) || left->left!=(void*) && right->right!=(void*) && isSymmetric(left->left,right->right)){        //左右子树都为空、或者对称

                 if(left->right==(void*) && right->left==(void*) ||left->right!=(void*) && right->left!=(void*) && isSymmetric(left->right,right->left))      //右左子树都为空、或对称

                     return true;

                 else

                     return false;

             }

             else    //左右子树不对称

                 return false;

         }

         else //左右结点值不等

             return false;

     }

 };

AC代码

python3：　　两种方法

　　增加默认参数。

 # Definition for a binary tree node.

 # class TreeNode(object):

 #     def __init__(self, x):

 #         self.val = x

 #         self.left = None

 #         self.right = None

 class Solution(object):

     def isSymmetric(self, root, right=None, isroot=True):

         """

         :type root: TreeNode

         :rtype: bool

         """

         F=self.isSymmetric

         if isroot==True:    #根

             if root==None:    return True

             return F(root.left, root.right, False)

         elif root==None and right==None:    #都是空

             return True

         elif root and right and root.val==right.val:    #都不空

             return F(root.left, right.right, False) and F(root.right, right.left, False)

         return False

AC代码

　　在函数中定义辅助函数。

 # Definition for a binary tree node.

 # class TreeNode(object):

 #     def __init__(self, x):

 #         self.val = x

 #         self.left = None

 #         self.right = None

 class Solution(object):

     def isSymmetric(self, root):

         """

         :type root: TreeNode

         :rtype: bool

         """

         def help(L, R):

             if not L and not R:

                 return True

             elif L and R and L.val==R.val:

                 return help(L.left,R.right) and help(L.right,R.left)

             else:

                 return False

         if root==None:    return True

         return help(root.left, root.right)

AC代码

巴特西

LeetCode OJ Symmetric Tree 判断是否为对称树（AC代码）

最新文章

热门文章