左右二叉树
2020-12-19 本文已影响0人
程序员乔戈里
题目
思路
找到递归点：左树与右树对称与否，与其跟两树的子树的对称情况有关系。
递归结束条件：
- 都为空指针则返回 true
- 只有一个为空则返回 false
- 两个指针当前节点值不相等 返回false
递归过程：
- 判断 A 的右子树与 B 的左子树是否对称
- 判断 A 的左子树与 B 的右子树是否对称
图解思路
代码实现
C++
class Solution {
public:
bool compare(TreeNode* left, TreeNode* right) {
// 首先排除空节点的情况
if (left == NULL && right != NULL) return false;
else if (left != NULL && right == NULL) return false;
else if (left == NULL && right == NULL) return true;
// 排除了空节点，再排除数值不相同的情况
else if (left->val != right->val) return false;
// 此时就是：左右节点都不为空，且数值相同的情况
// 此时才做递归，做下一层的判断
bool outside = compare(left->left, right->right); // 左子树：左、 右子树：右
bool inside = compare(left->right, right->left); // 左子树：右、 右子树：左
bool isSame = outside && inside; // 左子树：中、 右子树：中 （逻辑处理）
return isSame;
}
bool isSymmetric(TreeNode* root) {
if (root == NULL) return true;
return compare(root->left, root->right);
}
};
Java
public boolean isSymmetric(TreeNode root) {
if (root == null)
return true;
//从两个子节点开始判断
return isSymmetricHelper(root.left, root.right);
}
public boolean isSymmetricHelper(TreeNode left, TreeNode right) {
//如果左右子节点都为空，说明当前节点是叶子节点，返回true
if (left == null && right == null)
return true;
//如果当前节点只有一个子节点或者有两个子节点，但两个子节点的值不相同，直接返回false
if (left == null || right == null || left.val != right.val)
return false;
//然后左子节点的左子节点和右子节点的右子节点比较，左子节点的右子节点和右子节点的左子节点比较
return isSymmetricHelper(left.left, right.right) && isSymmetricHelper(left.right, right.left);
}
Python
class Solution(object):
def isSymmetric(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
if not root:
return True
def dfs(left,right):
# 递归的终止条件是两个节点都为空
# 或者两个节点中有一个为空
# 或者两个节点的值不相等
if not (left or right):
return True
if not (left and right):
return False
if left.val!=right.val:
return False
return dfs(left.left,right.right) and dfs(left.right,right.left)
# 用递归函数，比较左节点，右节点
return dfs(root.left,root.right)
Js
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {boolean}
*/
var isSame = function(root1,root2){
let r1,r2;
if(root1==null || root2==null)
{
if(root1==null && root2==null)
return true;
else
return false;
}
if(root1.val!==root2.val)
return false;
r1 = isSame(root1.left,root2.right);
r2 = isSame(root1.right,root2.left);
return r1 & r2;
}
var isSymmetric = function(root) {
if(root == null)
return true;
//判断根左子树是否和根右子树对称 递归的那l.left和r.right 以及 l.right 和r.left比较
return isSame(root.left,root.right);
};
迭代法
这道题目我们也可以使用迭代法，但要注意，这里的迭代法可不是前中后序的迭代写法，因为本题的本质是判断两个树是否是相互翻转的，其实已经不是所谓二叉树遍历的前中后序的关系了。
这里我们可以使用队列来比较两个树（根节点的左右子树）是否相互翻转，（注意这不是层序遍历）
使用队列
通过队列来判断根节点的左子树和右子树的内侧和外侧是否相等，如动画所示：
class Solution {
public:
bool isSymmetric(TreeNode* root) {
if (root == NULL) return true;
queue<TreeNode*> que;
que.push(root->left); // 将左子树头结点加入队列
que.push(root->right); // 将右子树头结点加入队列
while (!que.empty()) { // 接下来就要判断这这两个树是否相互翻转
TreeNode* leftNode = que.front(); que.pop();
TreeNode* rightNode = que.front(); que.pop();
if (!leftNode && !rightNode) { // 左节点为空、右节点为空，此时说明是对称的
continue;
}
// 左右一个节点不为空，或者都不为空但数值不相同，返回false
if ((!leftNode || !rightNode || (leftNode->val != rightNode->val))) {
return false;
}
que.push(leftNode->left); // 加入左节点左孩子
que.push(rightNode->right); // 加入右节点右孩子
que.push(leftNode->right); // 加入左节点右孩子
que.push(rightNode->left); // 加入右节点左孩子
}
return true;
}
};
使用栈
class Solution {
public:
bool isSymmetric(TreeNode* root) {
if (root == NULL) return true;
stack<TreeNode*> st; // 这里改成了栈
st.push(root->left);
st.push(root->right);
while (!st.empty()) {
TreeNode* leftNode = st.top(); st.pop();
TreeNode* rightNode = st.top(); st.pop();
if (!leftNode && !rightNode) {
continue;
}
if ((!leftNode || !rightNode || (leftNode->val != rightNode->val))) {
return false;
}
st.push(leftNode->left);
st.push(rightNode->right);
st.push(leftNode->right);
st.push(rightNode->left);
}
return true;
}
};
