Skip to content

Latest commit

 

History

History
346 lines (279 loc) · 10.9 KB

0100.相同的树.md

File metadata and controls

346 lines (279 loc) · 10.9 KB

参与本项目,贡献其他语言版本的代码,拥抱开源,让更多学习算法的小伙伴们受益!

100. 相同的树

力扣题目链接

给定两个二叉树,编写一个函数来检验它们是否相同。

如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。

思路

101.对称二叉树中,我们讲到对于二叉树是否对称,要比较的是根节点的左子树与右子树是不是相互翻转的,理解这一点就知道了其实我们要比较的是两个树(这两个树是根节点的左右子树),所以在递归遍历的过程中,也是要同时遍历两棵树。

理解这一本质之后,就会发现,求二叉树是否对称,和求二叉树是否相同几乎是同一道题目。

如果没有读过二叉树:我对称么?这一篇,请认真读完再做这道题,就会有感觉了。

递归三部曲中:

  1. 确定递归函数的参数和返回值

我们要比较的是两个树是否是相互相同的,参数也就是两个树的根节点。

返回值自然是bool类型。

代码如下:

bool compare(TreeNode* tree1, TreeNode* tree2)

分析过程同101.对称二叉树

  1. 确定终止条件

要比较两个节点数值相不相同,首先要把两个节点为空的情况弄清楚!否则后面比较数值的时候就会操作空指针了。

节点为空的情况有:

  • tree1为空,tree2不为空,不对称,return false
  • tree1不为空,tree2为空,不对称 return false
  • tree1,tree2都为空,对称,返回true

此时已经排除掉了节点为空的情况,那么剩下的就是tree1和tree2不为空的时候:

  • tree1、tree2都不为空,比较节点数值,不相同就return false

此时tree1、tree2节点不为空,且数值也不相同的情况我们也处理了。

代码如下:

if (tree1 == NULL && tree2 != NULLreturn false;
else if (tree1 != NULL && tree2 == NULLreturn false;
else if (tree1 == NULL && tree2 == NULLreturn true;
else if (tree1->val != tree2->val) return false; // 注意这里我没有使用else

分析过程同101.对称二叉树

  1. 确定单层递归的逻辑
  • 比较二叉树是否相同 :传入的是tree1的左孩子,tree2的右孩子。
  • 如果左右都相同就返回true ,有一侧不相同就返回false 。

代码如下:

bool left = compare(tree1->left, tree2->left);   // 左子树:左、 右子树:左
bool right = compare(tree1->right, tree2->right);  // 左子树:右、 右子树:右
bool isSame = left && right;                    // 左子树:中、 右子树:中(逻辑处理)
return isSame;

最后递归的C++整体代码如下:

class Solution {
public:
    bool compare(TreeNode* tree1, TreeNode* tree2) {
        if (tree1 == NULL && tree2 != NULLreturn false;
        else if (tree1 != NULL && tree2 == NULLreturn false;
        else if (tree1 == NULL && tree2 == NULLreturn true;
        else if (tree1->val != tree2->valreturn false; // 注意这里我没有使用else

        // 此时就是:左右节点都不为空,且数值相同的情况
        // 此时才做递归,做下一层的判断
        bool left = compare(tree1->left, tree2->left);   // 左子树:左、 右子树:左
        bool right = compare(tree1->right, tree2->right);  // 左子树:右、 右子树:右
        bool isSame = left && right;                    // 左子树:中、 右子树:中(逻辑处理)
        return isSame;

    }
    bool isSameTree(TreeNode* p, TreeNode* q) {
        return compare(p, q);
    }
};

我给出的代码并不简洁,但是把每一步判断的逻辑都清楚的描绘出来了。

如果上来就看网上各种简洁的代码,看起来真的很简单,但是很多逻辑都掩盖掉了,而题解可能也没有把掩盖掉的逻辑说清楚。

盲目的照着抄,结果就是:发现这是一道“简单题”,稀里糊涂的就过了,但是真正的每一步判断逻辑未必想到清楚。

当然我可以把如上代码整理如下:

递归

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;
        else return compare(left->left, right->left) && compare(left->right, right->right);

    }
    bool isSameTree(TreeNode* p, TreeNode* q) {
        return compare(p, q);
    }
};

迭代法

class Solution {
public:

    bool isSameTree(TreeNode* p, TreeNode* q) {
        if (p == NULL && q == NULL) return true;
        if (p == NULL || q == NULL) return false;
        queue<TreeNode*> que;
        que.push(p);   //  添加根节点p
        que.push(q);  //  添加根节点q
        while (!que.empty()) {  //
            TreeNode* leftNode = que.front(); que.pop();
            TreeNode* rightNode = que.front(); que.pop();
            if (!leftNode && !rightNode) {  // 若p的节点与q的节点都为空
                continue;
            }
            // 若p的节点与q的节点有一个为空或p的节点的值与q节点不同
            if ((!leftNode || !rightNode || (leftNode->val != rightNode->val))) {
                return false;
            }
            que.push(leftNode->left);   // 添加p节点的左子树节点
            que.push(rightNode->left); // 添加q节点的左子树节点
            que.push(leftNode->right);  // 添加p节点的右子树节点
            que.push(rightNode->right);  // 添加q节点的右子树节点
        }
        return true;
    }
};

其他语言版本

Java:

// 递归法
class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) return true;
        else if (q == null || p == null) return false;
        else if (q.val != p.val) return false;
        return isSameTree(q.left, p.left) && isSameTree(q.right, p.right);
    }
}
// 迭代法
class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p == null && q == null) return true;
        if(p == null || q == null) return false;
        Queue<TreeNode> que= new LinkedList<TreeNode>();
        que.offer(p);
        que.offer(q);
        while(!que.isEmpty()){
            TreeNode leftNode = que.poll();
            TreeNode rightNode = que.poll();
            if(leftNode == null && rightNode == null) continue;
            if(leftNode == null || rightNode== null || leftNode.val != rightNode.val) return false;
            que.offer(leftNode.left);
            que.offer(rightNode.left);
            que.offer(leftNode.right);
            que.offer(rightNode.right);
        }
        return true;
    }
}

Python:

# 递归法
class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        if not p and not q: return True
        elif not p or not q: return False
        elif p.val != q.val: return False
        return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
# 迭代法
class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        if not p and not q: return True
        if not p or not q: return False
        que = collections.deque()
        que.append(p)
        que.append(q)
        while que:
            leftNode = que.popleft()
            rightNode = que.popleft()
            if not leftNode and not rightNode: continue 
            if not leftNode or not rightNode or leftNode.val != rightNode.val: return False 
            que.append(leftNode.left)
            que.append(rightNode.left)
            que.append(leftNode.right)
            que.append(rightNode.right)
        return True

Go:

递归法

func isSameTree(p *TreeNode, q *TreeNode) bool {
    if p != nil && q == nil {
        return false
    }
    if p == nil && q != nil {
        return false
    }
    if p == nil && q == nil {
        return true
    }
    if p.Val != q.Val {
        return false
    }
    Left := isSameTree(p.Left, q.Left)
    Right := isSameTree(p.Right, q.Right)
    return Left && Right
}

JavaScript:

递归法

var isSameTree = function (p, q) {
    if (p == null && q == null)
        return true;
    if (p == null || q == null)
        return false;
    if (p.val != q.val)
        return false;
    return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
};

迭代法

var isSameTree = (p, q) => {
    const queue = [{ p, q }];
    // 这是用{ } 解决了null的问题!
    while (queue.length) {
        const cur = queue.shift();
        if (cur.p == null && cur.q == null) continue;
        if (cur.p == null || cur.q == null) return false;
        if (cur.p.val != cur.q.val) return false;
        queue.push({
            p: cur.p.left,
            q: cur.q.left
        }, {
            p: cur.p.right,
            q: cur.q.right
        });
    }
    return true;
};

TypeScript:

递归法-先序遍历

function isSameTree(p: TreeNode | null, q: TreeNode | null): boolean {
    if (p === null && q === null) return true;
    if (p === null || q === null) return false;
    if (p.val !== q.val) return false;
    return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
};

迭代法-层序遍历

function isSameTree(p: TreeNode | null, q: TreeNode | null): boolean {
    const queue1: (TreeNode | null)[] = [],
        queue2: (TreeNode | null)[] = [];
    queue1.push(p);
    queue2.push(q);
    while (queue1.length > 0 && queue2.length > 0) {
        const node1 = queue1.shift(),
            node2 = queue2.shift();
        if (node1 === null && node2 === null) continue;
        if (
            (node1 === null || node2 === null) ||
            node1!.val !== node2!.val
        ) return false;
        queue1.push(node1!.left);
        queue1.push(node1!.right);
        queue2.push(node2!.left);
        queue2.push(node2!.right);
    }
    return true;
};