树——对称二叉树

leetcode题目地址

1. 树为空树，亦为对称二叉树
2. 树非空时，仅需判断其左右子树是否对称
3. 判断左右子树对称
   (1) 左右子树是否为空，有一个为空 便不对称， 都为空或都不为空 可能对称
(2) 左右子树根节点值是否相同
(3) 判断 左子树 的 左子树 与 右子树 的右子树 是否相同
(4) 判断 左子树 的 右子树 与 右子树 的左子树 是否相同

递归方式

class Solution {
public:bool isSymmetric(TreeNode* root) {if( !root ) return true;return dfs(root->left,root->right);}bool dfs(TreeNode * l, TreeNode * r){if(!l || !r)return !l && !r;if(l->val != r->val)return false;return dfs(l->left,r->right) && dfs(l->right,r->left);}
};

迭代方式

class Solution {
public:bool isSymmetric(TreeNode* root) {if(!root) return true;stack<TreeNode*> l , r;auto p = root->left , q = root->right;while(p || q || l.size() || r.size()){while(p && q){l.push(p); p = p->left;r.push(q); q = q->right;}if( p || q)return false;p = l.top() , l.pop();q = r.top() , r.pop();if(p->val != q->val) return false;p = p->right;q = q->left;}return true;}
};

1. 采用类似中序遍历方式迭代
2. 对根节点的左子树进行 左 根 右 的方式遍历
3. 对根节点的右子树进行 右 根 左 的方式遍历
4. 2和3中的遍历同时进行
5. 一旦发现 二者在 第一次遍历至 树的最深 处时 ，不一致 ，即返回false
6. 一旦发现 二者在 栈顶 数值 不一致 ，即返回false

中序遍历迭代方式一

class Solution {
public:vector<int> inorderTraversal(TreeNode* root) {vector<int> res;stack<TreeNode*> s;while(root || s.size()){if( root ){s.push(root);root = root->left;}else{root = s.top() , s.pop();res.push_back(root->val);root = root->right;}}return res;}
};

中序遍历迭代方式二

class Solution {
public:vector<int> inorderTraversal(TreeNode* root) {vector<int> res;stack<TreeNode*> s;while(root || !s.empty()){while(root){s.push(root);root = root->left;}root = s.top() , s.pop();res.push_back(root->val);root = root->right;}return res;}
};