leetcode解题中一次坎坷的经历

一开始想的是用二叉树的遍历，左边中序遍历（左中右）一次，右边中序遍历（右中左）一次，之后2次遍历的结果比较是否相同。

Java代码

class Solution {
    public boolean isSymmetric(TreeNode root) {
        // 一开始的思路，但是很快发现问题，这样做根本不能判断是否轴对称
        // if (root.left == null && root.right == null)
        // return true;
        // if()
        // if (root.left != null && root.right == null) {
        // root.val += root.left.val;
        // return false;
        // } else if (root.right != null && root.left == null) {
        // root.val += root.right.val;
        // return false;
        // } else if (root.left != null && root.right != null && root.left.val ==
        // root.right.val) {
        // return true;
        // } else if (isSymmetric(root.left) && isSymmetric(root.right))
        // return true;
        // else
        // return false;
        // 之后的思路是左右子树都中序遍历，看结果是否一样
        // if (root == null)// 单个节点左右两个空子树当然轴对称
        // return true;
        if (root.left == null && root.right == null)
            return true;
        String left = "", right = "";
         InOrderLeft(root.left, left);
         InOrderRight(root.right, right);
         if (left.equals(right))
             return true;
        return false;
    }

    public void InOrderLeft(TreeNode root, String str) {
        
        if (root == null)
            return;
        InOrderLeft(root.left, str);
        str += root.val;
        
        InOrderLeft(root.right, str);
    }
    
    public void InOrderRight(TreeNode root, String str) {
        
        if (root == null)
            return;
            InOrderRight(root.right, str);
        str += root.val;
        
        InOrderRight(root.left, str);
    }
}

C++代码

#include 
class Solution
{
public:
    std::string left = "", right = "";
    bool isSymmetric(TreeNode *root)
    {
        if (root->left == nullptr && root->right == nullptr)
            return true;
        std::string left = "", right = "";
        InOrderLeft(root->left, left);
        InOrderRight(root->right, right);
        if (left==right)
            return true;
        return false;
    }

    void InOrderLeft(TreeNode *root, std::string &str)
    {
        if (root == nullptr)
            return;
        InOrderLeft(root->left, str);
        str += root->val;

        InOrderLeft(root->right, str);
    }
    void InOrderRight(TreeNode *root, std::string &str)
    {
        if (root == nullptr)
            return;
        InOrderRight(root->right, str);
        str += root->val;
        InOrderRight(root->left, str);
        
    }
};

但是提交后通过测试用例 195 / 198 个，一看错误用例是[1,2,2,2,null,2]

居然还有结点权重一样的…

于是准备写递归。

递归本身思路很简单，但问题的难点是二叉树是否对称取决于2个因素：

• 左右子树权重是否相等
• 左右子树树形结构是否完全相同

第一条只需判断val的值即可，但是第二条就比较麻烦。思来想去觉得只靠isSymmetric函数不够用，必须要写一个传入左右子树根结点作为参数的函数。后来去翻了翻评论区，恍然大悟，原来通过判断左子树的左边和右子树的右边对称，左子树的右边和右子树的左边对称即可。

最终通过代码

public boolean isSymmetric(TreeNode root) {
        return isMirror(root.left, root.right);
    }

    
    public boolean isMirror(TreeNode left, TreeNode right) {
        if (left == null && right == null)// 左右子树都为空，说明是叶子结点
            return true;
        else if (left == null || right == null)// 左右子树有一个是空，必然左右子树不等
            return false;
        else if (left.val == right.val)
            // 左子树的左边和右子树的右边对称，左子树的右边和右子树的左边对称
            return isMirror(left.left, right.right) && isMirror(left.right, right.left);
        else
            return false;
    }