首页 > 代码库 > [LeetCode OJ] Symmetric Tree

[LeetCode OJ] Symmetric Tree

2024-07-08 12:16:19   222人阅读

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree is symmetric:

    1   /   2   2 / \ / 3  4 4  3

But the following is not:

    1   /   2   2   \      3    3

Note:
Bonus points if you could solve it both recursively and iteratively.

confused what "{1,#,2,3}" means?

 

方法一：递归实现

 1 /** 2  * Definition for binary tree 3  * struct TreeNode { 4  *     int val; 5  *     TreeNode *left; 6  *     TreeNode *right; 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8  * }; 9  */10  bool canBeSymmetric(TreeNode *p, TreeNode *q)11  {12      if(p==NULL && q==NULL)13          return true;14      if((p==NULL && q!=NULL) || (p!=NULL && q==NULL))15          return false;16          17      if(p->val != q->val)18          return false;19      bool b1 = canBeSymmetric(p->left, q->right);  //若二叉树p和二叉树q对称，则 p 的左子树和 q 的右子树对称20      if(b1==false)21         return false;22      bool b2 = canBeSymmetric(p->right, q->left);  //若二叉树p和二叉树q对称，则 p 的右子树和 q 的左子树对称23      24      return b2;25  26  }27  28 class Solution {29 public:30     bool isSymmetric(TreeNode *root) {31         32         if(root==NULL)33             return true;34         35         return canBeSymmetric(root->left, root->right);36     }37 };

 

方法二：迭代实现

 1 /** 2  * Definition for binary tree 3  * struct TreeNode { 4  *     int val; 5  *     TreeNode *left; 6  *     TreeNode *right; 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8  * }; 9  */10  vector<int> PreOrderTraverse(TreeNode *p)  //按根左右的顺序遍历二叉树，迭代实现11  {12      vector<int> result;13      stack<TreeNode*> st;14      15      while(p || !st.empty())16      {17          if(p)18          {19              result.push_back(p->val);20              st.push(p);21              p = p->left;22          }23          else24          {25              result.push_back(0); //用0表示空树26              p = st.top();27              st.pop();28              p = p->right;29          }30      }31      result.push_back(0);32      return result;33  }34  35  vector<int> ReversePreOrderTraverse(TreeNode *p) //按根右左的顺序遍历二叉树，迭代实现36  {37      vector<int> result;38      stack<TreeNode*> st;39      40      while(p || !st.empty())41      {42          if(p)43          {44              result.push_back(p->val);45              st.push(p);46              p = p->right;47          }48          else49          {50              result.push_back(0); //用0表示空树51              p = st.top();52              st.pop();53              p = p->left;54          }55      }56      result.push_back(0);57      return result;58  }59  60  61 class Solution {62 public:63     bool isSymmetric(TreeNode *root) {64         65         if(root==NULL)66             return true;67         68         vector<int> ivec1 = PreOrderTraverse(root->left);69         vector<int> ivec2 = ReversePreOrderTraverse(root->right);70         71         return ivec1==ivec2;72     }73 };

 

注：

    发现对于两棵完全相同的二叉树，用"#"(方法二中是用整数0，也可以用其他的代替)代替空树，他们的先序遍历序列是完全相同的，

反之也成立，即若两颗二叉树的先序遍历序列（用"#"代替空树）完全相同，那么这两颗二叉树也必然相同。

 

然而这一事实对于用中序遍历序列则不成立，也就是说若两颗二叉树的中序遍历序列（用"#"代替空树）完全相同，这两颗二叉树不一定相同。举例如下：

  2 /           的中序遍历序列（左根右）为：  #3#2#            先序遍历序列（根左右）为： 23###          后序遍历序列（左右根）为： ##3#23                                                                 
不同                   相同                              不同                           不同
 3  \          的中序遍历序列（左根右）为：  #3#2#            先序遍历序列（根左右）为： 3#2##          后序遍历序列（左右根）为： ###23   2 

这两颗树不同，但他们对应的中序遍历序列却相同。


联系
我们