c_101_Symmetric_Tree

Posted on | In |

//
// Created by Mr.Hu on 2018/11/12.
//
// leetcode 101 symmetric tree
//
// 题目要求判断给定的二叉树是否为对称树，即根节点的左右儿子相等，
// 内部节点的左儿子节点值等于其兄弟节点的右节点值，
// 内部节点的右儿子节点值等于其兄弟节点的左节点值。如果为空节点，也是对称位置为空
//
// solution1：使用先序遍历，深度优先搜索实现，利用两个栈来存储待访问节点的信息，
// 要求第一个栈在存储当前待访问节点的左右子节点时，先存储左节点，再存储右节点；
// 第二个栈在存储当前待访问节点的左右子节点时，先存储右节点，再存储左节点；空节点也存储。
// 这样做的原因就是首先将该树考虑称满二叉树，然后当分别取两个栈的栈顶元素时，来自于对称位置的节点
//
// solution2：使用递归的方法，递归函数的参数为对称的两个节点
//

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <iostream>
#include <stack>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {};
};

class Solution {
public:
    bool recursive_body(TreeNode *node1, TreeNode *node2) {
        if (node1 != nullptr && node2 != nullptr) {
                return (node1->val == node2->val)
                    && recursive_body(node1->left, node2->right) 
                    && recursive_body(node1->right, node2->left);
        } else {
            return node1 == nullptr && node2 == nullptr;
        }
    }
    // recursively
    bool isSymmetric_recursively(TreeNode *root) {
        return recursive_body(root->left, root->right);
    }

    // iteratively
    bool isSymmetric_iteratively(TreeNode *root) {
        stack<TreeNode *> stack1, stack2;
        if (root != nullptr) {
            stack1.push(root);
            stack2.push(root);
        } else {
            return true;
        }
        while (!stack1.empty() && !stack2.empty()) {
            TreeNode *top_node1 = stack1.top();
            TreeNode *top_node2 = stack2.top();
            stack1.pop();
            stack2.pop();
            if (top_node1 != nullptr && top_node2 != nullptr) {
                if (top_node1->val == top_node2->val) {
                    stack1.push(top_node1->left);
                    stack1.push(top_node1->right);
                    stack2.push(top_node2->right);
                    stack2.push(top_node2->left);
                } else {
                    return false;
                }
            } else if (top_node1 == nullptr && top_node2 == nullptr) {
                continue;
            } else {
                return false;
            }
        }
        return stack1.empty() && stack2.empty();
    }
};

int main() {
    TreeNode root(10);
    TreeNode left1(2);
    TreeNode right1(2);
    TreeNode left11(3);
    TreeNode left12(4);
    TreeNode right11(4);
    TreeNode right12(3);
    root.left = &left1;
    root.right = &right1;
    left1.left = &left11;
    left1.right = &left12;
    right1.left = &right11;
    right1.right = &right12;
    Solution solution;
//    bool result = solution.isSymmetric_iteratively(&root);
    bool result = solution.isSymmetric_recursively(&root);
    cout << "is symmetric tree?: " << result;
    return 0;
}