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

末蓝、 2022-06-08 01:27 144阅读 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);
    
        }
    };