leetcode 100. Same Tree 二叉树DFS深度优先遍历-蒲公英云

leetcode 100. Same Tree 二叉树DFS深度优先遍历

末蓝、 2022-06-08 01:27 272阅读 0赞

Given two binary trees, write a function to check if they are equal or not.

Two binary trees are considered equal if they are structurally identical and the nodes have the same value.

题意很简单，就是DFS深度优先遍历。

代码如下：

/* class TreeNode 
 {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
}*/
public class Solution 
{
    public boolean isSameTree(TreeNode p, TreeNode q) 
    {
        return isEqual(p,q);
    }
    //递归遍历二叉树
    private boolean isEqual(TreeNode p, TreeNode q) 
    {
        if(p==null && q==null)
            return true;
        else if(p==null && q!=null || p!=null && q==null )
            return false;
        else if(p.val==q.val)
            return isEqual(p.left, q.left) && isEqual(p.right, q.right);
        else 
            return false;
    }
}

下面是C++的做法，就是做一个DFS深度优先遍历的做法，很简单的

代码如下：

#include<iostream>
#include <vector>
using namespace std;
/*
struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
*/
class Solution 
{
public:
    bool isSameTree(TreeNode* p, TreeNode* q) 
    {
        if (p == NULL && q != NULL || p != NULL && q == NULL)
            return false;
        else if (p == NULL && q == NULL)
            return true;
        else if (p->val != q->val)
            return false;
        else 
            return isSameTree(p->left,q->left) && isSameTree(p->right,q->right);
    }
};