C++ 代码实现 反转二叉树、对称二叉树 后序遍历思想的应用

// 反转二叉树
void InvertTree(TreeNode *root){
    if (root == nullptr)
    {
        return;
    }
    std::swap<>(root->left, root->right); // 根
    InvertTree(root->left); // 左
    InvertTree(root->right); // 右
    // ---------------------------------------
    InvertTree(root->left); // 左
    InvertTree(root->right); // 右
    std::swap<>(root->left, root->right); // 根
    // ----------------------------------------
    InvertTree(root->left); // 左
    std::swap<>(root->left, root->right); // 根
    InvertTree(root->left); // 左
    // ---------------------------------------
    InvertTree(root->right); // 左
    std::swap<>(root->left, root->right); // 根
    InvertTree(root->right); // 左
}
//中序遍历时 交换左右孩子节点后，应仍旧沿着上一次遍历方向进行，
//这样才能恰恰和交换后要遍历的孩子节点对应 

// 对称二叉树
bool Compare(TreeNode *left, TreeNode *right){
    if (left != nullptr && right == nullptr)
    {
        return false;
    }else if (left == nullptr && right != nullptr)
    {
        return false;
    }else if (left == nullptr && right == nullptr)
    {
        return true;
    }else if (left->data != right->data)
    {
        return false;
    }
    bool left_left_right_right = Compare(left->left, right->right); // 左
    bool left_right_right_left = Compare(left->right, right->left); // 右
    return left_left_right_right && left_right_right_left; // 根
    // 为什么采取后序遍历？
    // 因为只有判断清楚左子树的左孩子和右子树的右孩子对称 且 
    // 左子树的右孩子和右子树的左孩子对称后，才能证实根节点对称
}

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