Symmetric Tree
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.
递归思路:
对左右子树分别深搜,不过左右子树的优先访问分支是相反的。
递归题解:
/** * 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 verify(TreeNode* L, TreeNode* R) { if (L == nullptr && R == nullptr) return true; else if (bool(L) ^ bool(R)) return false; else if (L->val != R->val) return false; else return verify(L->right, R->left) && verify(L->left, R->right); } bool isSymmetric(TreeNode *root) { if (root == nullptr) return true; return verify(root->left, root->right); } };
迭代思路:
按照行遍历,每一行都要考虑到有nullptr的可能,直到这一行的值都是nullptr为止。