/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
二叉树 后序遍历 递归 DFS
思路：对称二叉树，递归过程需要同时比较“外侧和内侧”两棵树，并将比较结果结合(&&)往回传递，
如果都为true则不说，如果有一次为false则一路往回都会返回false。
注：轴对称，需要考虑的是每次递归“外侧和内侧”的比较，狭隘地考虑比较每次root的左右节点，是不行的。
注：此题是一个好的例子，递归参数中往下传的不一定是root，也可能是left+right。
注：递归过程同时遍历left+right左右2个节点，看着唬人，其实也是符合逻辑的，比较对称问题，
不然应该如何比较轴对称呢。
注：此题可以看出，终止条件return是可以出现多个的，不仅仅是一个。“终止条件”考虑得比较多，要想清楚不能遗漏。
比如都比外侧的左右两个节点，它们如果一空一不空，直接false；如果都空，直接true；然后才是比值，如果val不同，
直接false。然后才是“内部逻辑”部分。
注：此题是“后续遍历”的变种，因为是有点类似左-右-中，实际上是外侧-内侧-中。
注：此题递归的返回类型是bool，属于“一层一层往回带出返回值”，也是常见的一种类型，
和之前返回root的情况不一样，这二者的区别在于“左右递归的时候，是否有返回值，并且会继续往回带”。
注：此题主函数最终的返回值，是递归函数的返回值，有时也可能是递归函数的参数，比如vec(result)这种。
注：递归三部曲。
1）参数和返回值。参数按如上所说，如果不是root，那么应该考虑到left+right进去递归。
此外，有时带个额外的参数，如vec(result)用来装结果，也是常见的。
2）终止条件。如上所说，不止一个终止条件，需要考虑清楚，几个“可以直接return的条件”都想到了，
再进入“内部逻辑”的部分。
3）内部逻辑。内部逻辑就是“外侧-内侧-中”，可见内部逻辑始终会包括“左右继续递归”这个关键部分。
然后就是“中的处理”，实际上中的处理是“比较淡化”的，而且“可能是没有固定套路和思想”的，
比如此题是直接“return左右继续递归的结果”。
class Solution {
public:
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->val != right->val) return false;
bool out_val = compare(left->left, right->right);
bool in_val = compare(left->right, right->left);
bool is_same = out_val && in_val;
return is_same;
}
bool isSymmetric(TreeNode* root) {
if (root == nullptr) return true;
bool result = compare(root->left, root->right);
return result;
}
};
// @lc code=end
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
自己写一遍，会考察
// struct TreeNode {
// int val;
// TreeNode* left;
// TreeNode* right;
// TreeNode() : val(0), left(nullptr), right(nullptr) {}
// TreeNode(int v) : val(v), left(nullptr), right(nullptr) {}
// TreeNode(int v, TreeNode* l, TreeNode* r) : val(v), left(l), right(r) {}
// };
复习：怎么判断一棵树是否对称，首先，如果root节点为空，则对称，如果不为空，则需要进一步判断左子树、右子树。怎么判断根节点的左右子树是否对称，主要包括3个步骤，第1步是左边节点val=右边节点val，第2步是左子树节点的左子树=右子树边节点的右子树，第3步是左子树节点的右子树=右子树边节点的左子树，此时又面临xxx节点的左子树？=xxx节点的右子树之类的问题，这就是“递归”的表现了。
发现问题的关键：怎么判断xxx节点的左右子树是否对称？需要写一个递归函数，入参是左右节点，并在其内部调用自己。
xxx isLeftRightEqual(left, right) {}
首先考虑一个3层的树（完整的树，没有null的分支，且完全对称，后面再考虑有null分支啊、不对称啊），那么一上来，这几句话是比较容易想到的，这也是刚才整理的3个步骤：（递归三部曲的“内部逻辑”）
1）if (left->val ？= right->val) 节点判断
2）isLeftRightEqual(left->left, right->right); 节点往下的外层判断
3）isLeftRightEqual(left->right, right->left); 节点往下的内层判断
对于这棵树而言，1）会通过，2）会一直递归进入，直到最深入底层，3）暂不考虑。那么，此时当到第4层时，就会遇到left和right都为空的时候了，此时怎么办呢？显然，就遇到了递归三部曲的“终止条件”，那么就应该想到，如果：
if (left == nullptr && right == nullptr)
return true; 因为对于当前这层，这个结果是ok的
此时有个比较重要的点，return true，这个过程应该想到，这个递归函数的三部曲的“返回值”xxx应该不是void，而是有值的，是bool，递归函数的返回值是有“叠加返回的功效的”，这一点心里需要稍微有所预期，进而想到，这层返回了true，那么别的时候可能就会返回false。返回值一定是从2）3）这个调用递归函数的位置“取得结果的”，而当前层bool的返回，除了“终止条件”里的A return可以返回，2）3）后的B return也是可以返回的，所以返回是有两种通路，并且，B return的返回，往往带有某种“处理性质，也就是会将2）3）的返回结果进行综合处理”，而2）3）的返回结果可能直接来自于A return，也可能来自于B return，最初一定是来自于递归最深处“终止条件”的A return的。
说回上文，以下逻辑也比较容易想到，当左右不同时为空时，则当前层（外or内）是不ok的
} else if (left == nullptr && right != nullptr) {
return false;
} else if (left != nullptr && right == nullptr) {
return false;
判空保护做完以后，才到了我们的1）登场，如果节点值不同，那么不ok
} else if (left->val != right->val) {
return false;
最后，如果上述条件都通过了，那么（其实此时就回到我们最初尝试2）），外层一路向下递归的情况
bool flag_outer = isLeftRightEqual(left->left, right->right);
bool flag_innter = isLeftRightEqual(left->right, right->left);
基于刚才的考虑，我们应该拿一个flag来承接2）3）返回的值，并在当前层B return的时候，将flag进行“综合处理”，显然，一路递归的过程中，要每一层的节点、外层、内层、如果有空得同时空，这些条件都满足，最终才能为true，而中间过程一旦出现一个false，都是无法ok的，所以，“综合处理”需要将每层的左右结果&&起来，一旦从“终止条件”中有1个false出现，那么就一定会被从A return返回到2）or3）的结果中，进而在“综合处理”时，通过B return进一步返回该false，再到上一层的2）or3）那去，最终返回到最外层main函数调用递归函数那去，此时就确定该树不对称！
此题虽然没有直接的“左-右-中”后续遍历，但却有“外侧-内侧-中”的思想，其实“中”就是我们的“综合处理”，可能是B return，但如果是void递归，就也可能是vec.push_back()这类收集形式，需要灵活变化一下。
此题递归三部曲的掌握仍是关键！
此外，此题下面注释的部分，如果直接通过vec的形式，中序or后序or其他方式遍历一遍，比如“左-右-中vec装”，然后“右-左-中vec装”，如果对称，那么看上去vec装的结果是一样的，最后通过对比vec的结果来判断是否对称。这种思路能对一部分，但遇到空分支就行不通了，比如“1 空 2” “1 2 空”会被当成一样的，因为空会跳过，所以上述都会被当成“1 2”
class Solution {
public:
// void traverseLeft(TreeNode* root, vector<int>& vec) {
// if (root == nullptr) return;
// traverseLeft(root->left, vec);
// traverseLeft(root->right, vec);
// vec.push_back(root->val);
// }
// void traverseRight(TreeNode* root, vector<int>& vec) {
// if (root == nullptr) return;
// traverseRight(root->right, vec);
// traverseRight(root->left, vec);
// vec.push_back(root->val);
// }
bool isLeftRightEqual(TreeNode* left, TreeNode* right) {
if (left == nullptr && right == nullptr) {
return true;
} else if (left == nullptr && right != nullptr) {
return false;
} else if (left != nullptr && right == nullptr) {
return false;
} else if (left->val != right->val) {
return false;
} else {
bool flag_outer = isLeftRightEqual(left->left, right->right);
bool flag_innter = isLeftRightEqual(left->right, right->left);
return flag_outer && flag_innter;
}
}
bool isSymmetric(TreeNode* root) {
// vector<int> result_left;
// vector<int> result_right;
// traverseLeft(root, result_left);
// traverseRight(root, result_right);
// if (result_left == result_right) {
// return true;
// } else {
// return false;
// }
if (root == nullptr) return true;
return isLeftRightEqual(root->left, root->right);
}
};
