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)$ 。

巴特西

C#LeetCode刷题之#100-相同的树（Same Tree）

最新文章

热门文章