首页 > 代码库 > Leetcode#101 Symmetric Tree

Leetcode#101 Symmetric Tree

2024-11-17 08:31:02   202人阅读

原题地址

 

有人些的做法是判断中序遍历序列是否是回文串，一开始我觉得挺有道理，但是琢磨了一阵觉得没那么简单。

比如下面这个树：

         1
        /
       1
      /
     1

中序遍历序列是"111"，虽然是回文串但这棵树明显不是对称的。

如果要是把NULL也算进去呢？还是上面那棵树，现在变成了这样：

         1
        / \
       1  NULL
      / \
     1  NULL
    / \
 NULL NULL

中序遍历序列为："N1N1N1N"，看吧，还是错的。

如果只计算非叶结点的NULL呢？还是上面那棵树，现在变成了这样：

         1
        / \
       1  NULL
      / \
     1  NULL

中序遍历序列为："11N1N"，这个例子是没问题了，不过不知道是不是对的。

总之，结论并没有那么"明显"，很容易想错。这个方法还有一个缺点，即必须保存整个数的遍历序列，空间复杂度是O(n)的，如果树很大，空间开销不小。

所以，不推荐上面这种方法。

 

推荐以下两种方法

方法I，二叉树的层次遍历

逐层遍历二叉树，判断该层是否是回文串，注意保存节点的序号信息

代码：

 1 bool isSymmetric(TreeNode *root) { 2   if (!root) return true; 3  4   vector<pair<TreeNode *, int> > layer; 5   layer.push_back(pair<TreeNode *, int>(root, 0)); 6  7   while (!layer.empty()) { 8     vector<pair<TreeNode *, int> > nextLayer; 9     for (int i = 0; i < layer.size(); i++) {10       if (layer[i].first->left)11         nextLayer.push_back(pair<TreeNode *, int>(layer[i].first->left, i * 2));12       if (layer[i].first->right)13         nextLayer.push_back(pair<TreeNode *, int>(layer[i].first->right, i * 2 + 1));14     }15     for (int i = 0, j = nextLayer.size() - 1; i <= j; i++, j--)16       if ((nextLayer[i].first->val != nextLayer[j].first->val)17           || (nextLayer[i].second + nextLayer[j].second != layer.size() * 2 - 1))18         return false;19     layer = nextLayer;20   }21 22   return true;23 }

 

 

方法II，递归比较（引用自这篇博文）

对于任意子树，比较根节点的：左儿子的左子树和右儿子的右子树是否对称，左儿子的右子树和右儿子的左子树是否对称

代码：

1 bool isSymmetric(TreeNode *root) {2   return root ? isSymmetric(root->left, root->right) : true;3 }4 5 bool isSymmetric(TreeNode *left, TreeNode *right) {6   if (!left && !right) return true; 7   if (!left || !right) return false; 8   return left->val == right->val && isSymmetric(left->left, right->right)&& isSymmetric(left->right, right->left);9 }

很巧妙

Leetcode#101 Symmetric Tree


联系
我们