leetcode筆記：Same Tree

leetcode筆記：Same Tree

一. 題目描述

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.

二. 題目分析

題目的意思很簡單，判斷兩棵樹是否相同，遞歸，對兩棵樹的結點進行比較即可。

三. 示例代碼

#include 

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)
            return true;
        // p和q不同時到達葉節點，則剪枝
        else if ((p != NULL && q == NULL) || (p == NULL && q != NULL))
            return false;
        return (p->val == q->val) && isSameTree(p->left, q->left)
               && isSameTree(p->right, q->right);
    }
};

四. 小結

該題屬於二叉樹的遍歷中的基礎題目，難度不大。