interviewalgo
, , , ,
Source
Edit
History

判断二叉树是否对称

Introduction

Question：判断二叉树是否对称

Analysis

一开始想复杂了，还以为一颗对称的树，其子树也需要满足对称（不过这样是不是还更好做一点）。这道题想起来并不复杂，可能在实现迭代版本的时候会略微有些繁琐。

其实只需要同时对两颗子树同时进行先序遍历即可，左子树执行正常的先序遍历，右子树执行先访问右子树再访问左子树的先序遍历。然后再遍历时做好判断即可。由于先序遍历实现迭代版本也不复杂，只需要借助一个栈即可。

Implement

递归版本

1
2
3
4
5
6
7
8
9
10
bool isSymmetric(TreeNode* left, TreeNode *right) {
    if (left == nullptr && right == nullptr) return true;
    else if (left && right && left->val == right->val) {
        return isSymmetric(left->left, right->right) && 
            isSymmetric(left->right, right->left);
    } else return false;
}
bool isSymmetric(TreeNode* root) {
    return root == nullptr || isSymmetric(root->left, root->right);
}

迭代版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
bool isSymmetric(TreeNode* root) {
    // 迭代版本
    if (root == nullptr) return true;
    TreeNode *left, *right;
    left = root->left;
    right = root->right;
    if ((left && !right) || (!left && right)) return false;
    // 先序遍历
    stack<TreeNode*> stLeft, stRight;
    while ((left && right) || (!stLeft.empty() && !stRight.empty())) {
        // visit node
        if ((left && !right) || (!left && right)) return false;
        else if (left && right) {
            if (left->val != right->val) return false;
            stLeft.push(left->right);
            stRight.push(right->left);
            left = left->left;
            right = right->right;
        } else {
            left = stLeft.top(); stLeft.pop();
            right = stRight.top(); stRight.pop();
        }
    }
    return true;
}

One More Thing