【Leetcode】100. 相同的树

栏目: 数据库 · 发布时间: 5年前

内容简介:给定两个二叉树,编写一个函数来检验它们是否相同。如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。示例 1:

题目

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

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

示例 1:

输入:       1         1
          / \       / \
         2   3     2   3

        [1,2,3],   [1,2,3]

输出: true
示例 2:
输入:      1          1
          /           \
         2             2

        [1,2],     [1,null,2]

输出: false
示例 3::
输入:       1         1
          / \       / \
         2   1     1   2

        [1,2,1],   [1,1,2]

输出: false

题解

大多数的二叉树题目都是用递归可以解的。

所以当拿到二叉树的题目的时候,我们首先就是看看能拆解成哪些子问题。

这个问题的子问题很简单,就是左子树,右子树都相等的二叉树是相同的二叉树。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        } else if (p == null || q == null) {
            return false;
        }
        
        if (p.val == q.val) {
            return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
        } else {
            return false;
        }
    }
}

那如果用非递归解怎么解呢?

如果遇到二叉树的问题,没思路还有第二招,就是 想想看是不是遍历的变种

  • 先序遍历
  • 中序遍历
  • 后序遍历
  • 层次遍历

我们可以用队列,一起进行层序遍历,同时比较左右两颗树:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        } else if (p == null || q == null) {
            return false;
        }

        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.add(p);
        queue.add(q);
        while(!queue.isEmpty()) {
            TreeNode left = queue.poll();
            TreeNode right = queue.poll();
            if (left == null && right == null) {
                // 都是空的,遍历到叶子节点了
                continue;
            } else if (left == null || right == null) {
                // 有一个为null
                return false;
            } else if (left.val != right.val) {
                // 不相等.
                return false;
            }
            // 左子树入队
            queue.add(left.left);
            queue.add(right.left);
            // 右子树入队
            queue.add(left.right);
            queue.add(right.right);
        }
        
        return true;
    }
}

其实我们本质上就是要比较左右两棵树,也没必要非要是队列,其实stack也是可以的,大同小异。所以并不是你记住哪种数据结构,关键是你能理解后,灵活应用.

public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        } else if (p == null || q == null) {
            return false;
        }

        Stack<TreeNode> stack = new Stack<>();
        stack.push(p);
        stack.push(q);
        while(!stack.isEmpty()) {
            TreeNode left = stack.pop();
            TreeNode right = stack.pop();
            if (left == null && right == null) {
                continue;
            } else if (left == null || right == null) {
                return false;
            } else if (left.val != right.val) {
                return false;
            }
            stack.push(left.left);
            stack.push(right.left);
            stack.push(left.right);
            stack.push(right.right);
        }
        return true;
    }

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

C++ How to Program (5th Edition) (How to Program)

C++ How to Program (5th Edition) (How to Program)

Harvey & Paul) Deitel & Associates / Prentice Hall / 2005-01-05 / USD 98.00

With over 250,000 sold, Harvey and Paul Deitel's C++ How to Program is the world's best-selling introduction to C++ programming. Now, this classic has been thoroughly updated! The Deitels' groundbreak......一起来看看 《C++ How to Program (5th Edition) (How to Program)》 这本书的介绍吧!

XML、JSON 在线转换
XML、JSON 在线转换

在线XML、JSON转换工具

RGB CMYK 转换工具
RGB CMYK 转换工具

RGB CMYK 互转工具

HSV CMYK 转换工具
HSV CMYK 转换工具

HSV CMYK互换工具