LeetCode 100. Same Tree (Tag : DFS)

1. 问题描述

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

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

翻译过来就是，给定两个二叉树，判断这两个树是否相同。

Example 1:

代码语言：javascript复制

Input:     1         1
         /        / 
        2   3     2   3       [1,2,3],   [1,2,3]
Output: true

Example 2:

代码语言：javascript复制

Input:     1         1
/           
2             2[1,2],     [1,null,2]
Output: false

2. 解题思路。

• 从根结点出发， 根据根结点的情况进行判断
  • 两个根结点都为null， 则相同，返回true。
  • 两个根结点中只有一个为null， 返回false。
  • 若两个根结点的值相等，则递归判断，节点1的左孩子，节点2的左孩子 && 节点1的右孩子，节点2的右孩子。

3. 代码

代码语言：javascript复制

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        // p, q 都为null
        if ( p == null && q == null) {
            return true;
        }
        // p, q 只有一个为null
        if ( p == null || q == null) {
            return false;
        }
        // p, q 值相等，递归判断孩子节点的情况
        if ( p.val == q.val ) {
            return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
        }
        return false;
    }
}

二叉树 binary function nodes null

0 人点赞