C#LeetCode刷题之#100-相同的树(Same Tree)

C#LeetCode刷题之#100-相同的树(Same Tree)

问题

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

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

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

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

输出: true

输入:      1          1
               /           \
             2             2

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

输出: false

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

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

输出: false

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.

Input:     1         1
              / \       / \
            2   3   2   3

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

Output: true

Input:     1         1
               /           \
             2             2

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

Output: false

Input:     1         1
               / \       / \
             2   1   1    2

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

Output: false

示例

public class Program {

    public static void Main(string[] args) {
        var p = new TreeNode(1) {
            left = new TreeNode(2)
        };

        var q = new TreeNode(1) {
            left = new TreeNode(2)
        };

        var res = IsSameTree(p, q);
        Console.WriteLine(res);

        q.right = new TreeNode(6);

        res = IsSameTree2(p, q);
        Console.WriteLine(res);

        Console.ReadKey();
    }

    public static void IsSame(TreeNode p, TreeNode q, ref bool isSameTree) {
        //先序遍历分析法
        if(p?.val != q?.val) {
            isSameTree = false;
            return;
        }
        if(p != null && q != null) {
            if(p.left != null || q.left != null) {
                IsSame(p.left, q.left, ref isSameTree);
            }
            if(p.right != null || q.right != null) {
                IsSame(p.right, q.right, ref isSameTree);
            }
        }
        return;
    }

    public static bool IsSameTree(TreeNode p, TreeNode q) {
        var isSameTree = true;
        IsSame(p, q, ref isSameTree);
        return isSameTree;
    }

    public static bool IsSameTree2(TreeNode p, TreeNode q) {
        //优雅递归法
        //如果 p 和 q 同时为空,则肯定相
        //已经到了递归最底层的调用,也就是递归的最基本情况
        //属于递归的终止条件
        //以下3行代码均是终止条件
        if(p == null && q == null) return true;
        //如果 p 为空,q 不为空,则肯定不相同
        if(p == null) return false;
        //如果 q 为空,p 不为空,则肯定不相同
        if(q == null) return false;
        //递归调用
        return p.val == q.val &&
                IsSameTree2(p.left, q.left) &&
                IsSameTree2(p.right, q.right);
    }

    public class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode(int x) { val = x; }
    }

}

以上给出2种算法实现,以下是这个案例的输出结果:

True
False

分析:

显而易见,以上2种算法的时间复杂度均为: O(n) 。

本文由 .Net中文网 原创发布,欢迎大家踊跃转载。

转载请注明本文地址:https://www.byteflying.com/archives/4066

发表评论

登录后才能评论