首页 > 代码库 > leetcode Symmetric Tree
leetcode Symmetric Tree
这里是给定一个数，判断是不是对称的，即根据根画一竖直线对折重合一样。
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.
这题标注是easy的题。但是试了好多次才想通。
错误的尝试一：以为是中序遍历一下，然后矩阵对称相等就行，实际是不行的，例如把上面第二个图中，右边的3和2调换位置，他的中序遍历结果是根据中心对称，但实际不是对称的。
错误的尝试二：以为对左子树中序遍历，对右子树反向中序遍历（右根左），如果两者一样就是对称。就如上面第二例子就bug了
然后静下心，好好想，既然标注easy，应该不那么复杂。终于被我想到了用递归的方法。其实不难，就是判断两个子树一个数的右边是不是等于另一个树的左边，依次类推。和上一题差不多。
/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public:bool isSym(TreeNode *p, TreeNode *q){ if (!p) return !q; if (!q) return !p; if (p -> val != q -> val) return false; bool flag = isSym(p -> left, q -> right); return flag && isSym(p -> right, q -> left);} bool isSymmetric(TreeNode *root) { if (!root) return true; if (!root -> left) return !root->right; if (!root -> right) return !root->left; return isSym(root->left, root->right); }};
leetcode Symmetric Tree
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。