1305.两棵二叉搜索树中的所有元素

链接：1305.两棵二叉搜索树中的所有元素
难度：Medium
标签：树、深度优先搜索、二叉搜索树、二叉树、排序
简介：请你返回一个列表，其中包含 两棵树 中的所有整数并按 升序 排序。

题解 1 - typescript

• 编辑时间：2021-05-13
• 执行用时：204ms
• 内存消耗：51.6MB
• 编程语言：typescript
• 解法介绍：归并。

function getAllElements(root1: TreeNode | null, root2: TreeNode | null): number[] {
  const inorder = (node: TreeNode | null, queue: number[]): void => {
    if (node === null) return;
    inorder(node.left, queue);
    queue.push(node.val);
    inorder(node.right, queue);
  };
  const queue1: number[] = [];
  inorder(root1, queue1);
  const queue2: number[] = [];
  inorder(root2, queue2);
  let p1 = 0;
  const len1 = queue1.length;
  let p2 = 0;
  const len2 = queue2.length;
  const ans: number[] = [];
  while (p1 < len1 || p2 < len2) {
    ans.push(p2 >= len2 || queue1[p1] <= queue2[p2] ? queue1[p1++] : queue2[p2++]);
  }
  return ans;
}

题解 2 - go

• 编辑时间：2022-05-01
• 执行用时：84ms
• 内存消耗：8.4MB
• 编程语言：go
• 解法介绍：dfs。

func getAllElements(root1 *TreeNode, root2 *TreeNode) []int {
  arr1 := getArr(root1)
  n1 := len(arr1)
  arr2 := getArr(root2)
  n2 := len(arr2)
  ans := make([]int, n1+n2)
  var i1, i2 = 0, 0
  for i := 0; i1 < n1 || i2 < n2; i++ {
    if i1 != n1 && (i2 == n2 || arr1[i1] < arr2[i2]) {
      ans[i] = arr1[i1]
      i1++
    } else {
      ans[i] = arr2[i2]
      i2++
    }
  }
  return ans
}
func getArr(node *TreeNode) (arr []int) {
  var dfs func(*TreeNode)
  dfs = func(node *TreeNode) {
    if node == nil {
      return
    }
    dfs(node.Left)
    arr = append(arr, node.Val)
    dfs(node.Right)
  }
  dfs(node)
  return arr
}

题解 3 - c

• 编辑时间：2022-05-01
• 执行用时：196ms
• 内存消耗：56.4MB
• 编程语言：c
• 解法介绍：dfs。

int *getAllElements(struct TreeNode *root1, struct TreeNode *root2,
  int *returnSize) {
    int n1 = 0, n2 = 0;
    int *arr1 = (int *)malloc(sizeof(int) * 5005);
    int *arr2 = (int *)malloc(sizeof(int) * 5005);
    createArr(arr1, &n1, root1);
    createArr(arr2, &n2, root2);
    *returnSize = 0;
    int *ans = (int *)malloc(sizeof(int) * (n1 + n2));
    for (int i1 = 0, i2 = 0; i1 < n1 || i2 < n2;) {
        if (i1 != n1 && (i2 == n2 || arr1[i1] < arr2[i2]))
            ans[(*returnSize)++] = arr1[i1++];
        else
            ans[(*returnSize)++] = arr2[i2++];
    }
    free(arr1);
    free(arr2);
    return ans;
}
void createArr(int *arr, int *size, struct TreeNode *node) {
    if (node == NULL) return;
    createArr(arr, size, node->left);
    arr[(*size)++] = node->val;
    createArr(arr, size, node->right);
}