石家庄网站推广专家,wordpress先页面再首页,网站服务器哪里的好,移动端ui设计leetcode题目地址
树为空树#xff0c;亦为对称二叉树树非空时#xff0c;仅需判断其左右子树是否对称判断左右子树对称 (1) 左右子树是否为空#xff0c;有一个为空 便不对称#xff0c; 都为空或都不为空 可能对称 (2) 左右子树根节点值是否相同 (3) 判断 左子树 的 左子…leetcode题目地址
树为空树亦为对称二叉树树非空时仅需判断其左右子树是否对称判断左右子树对称 (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;stackTreeNode* 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;}
};采用类似中序遍历方式迭代对根节点的左子树进行 左 根 右 的方式遍历对根节点的右子树进行 右 根 左 的方式遍历2和3中的遍历同时进行一旦发现 二者在 第一次遍历至 树的最深 处时 不一致 即返回false一旦发现 二者在 栈顶 数值 不一致 即返回false 中序遍历迭代方式一 class Solution {
public:vectorint inorderTraversal(TreeNode* root) {vectorint res;stackTreeNode* 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:vectorint inorderTraversal(TreeNode* root) {vectorint res;stackTreeNode* 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;}
};
