【小Y学算法】⚡️每日LeetCode打卡⚡️——26.相同的树

输入：p = [1,2,3], q = [1,2,3]
输出：true

输入：p = [1,2], q = [1,null,2]
输出：false

输入：p = [1,2,1], q = [1,1,2]
输出：false

public class Solution {
public bool IsSameTree(TreeNode p, TreeNode q)
        {
            //递归终止情况1：p, q都是null
            if (p == null && q == null)
            {
                return true;
            }
            //递归终止情况2：p, q中有一个为空，或者是p, q的节点值不等
            else if (p == null || q == null || p.val != q.val)
            {
                return false;
            }
            else
            {
                //递归看左子树是否相同
                bool isLeftSameTree = IsSameTree(p.left, q.left);
                //递归看右子树是否相同
                bool isRightSameTree = IsSameTree(p.right, q.right);
                return isLeftSameTree && isRightSameTree;
            }
        }
}

通过
执行用时：92 ms，在所有 C# 提交中击败了49.73%的用户
内存消耗：24.4 MB，在所有 C# 提交中击败了38.50%的用户

时间复杂度：O(min(m+n))
空间复杂度：O(min(m+n))

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        for (int i = 0; i != n; ++i) {
            nums1[m + i] = nums2[i];
        }
        Arrays.sort(nums1);
    }
}

通过
执行用时：0 ms，在所有 Java  提交中击败了100.00%的用户
内存消耗：35.8 MB，在所有 Java 提交中击败了53.34%的用户

时间复杂度：O(min(m+n))其中 mm 和 nn 分别是两个二叉树的节点数。对两个二叉树同时进行深度优先搜索，只有当两个二叉树中的对应节点都不为空时才会访问到该节点，因此被访问到的节点数不会超过较小的二叉树的节点数。

空间复杂度：O(min(m+n))其中 mm 和 nn 分别是两个二叉树的节点数。空间复杂度取决于递归调用的层数，递归调用的层数不会超过较小的二叉树的最大高度，最坏情况下，二叉树的高度等于节点数。

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int p1 = 0, p2 = 0;
        int[] sorted = new int[m + n];
        int cur;
        while (p1 < m || p2 < n) {
            if (p1 == m) {
                cur = nums2[p2++];
            } else if (p2 == n) {
                cur = nums1[p1++];
            } else if (nums1[p1] < nums2[p2]) {
                cur = nums1[p1++];
            } else {
                cur = nums2[p2++];
            }
            sorted[p1 + p2 - 1] = cur;
        }
        for (int i = 0; i != m + n; ++i) {
            nums1[i] = sorted[i];
        }
    }
}

通过
执行用时：0 ms，在所有 Java  提交中击败了100%的用户
内存消耗：35.7 MB，在所有 Java 提交中击败了72.26%的用户

时间复杂度：O(min(m+n))
空间复杂度：O(min(m+n))