Lstmxx的空间

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

给你 root1 和 root2 这两棵二叉搜索树。

请你返回一个列表，其中包含 两棵树 中的所有整数并按 升序 排序。.

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function getAllElements(root1: TreeNode | null, root2: TreeNode | null): number[] {
  const res: number[] = []
  const stack1: TreeNode[] = []
  const stack2: TreeNode[] = []

  while((root1 !== null || stack1.length !== 0) && (root2 !== null || stack2.length !== 0)) {
    while(root1 !== null) {
      stack1.push(root1)
      root1 = root1.left
    }
    while(root2 !== null) {
      stack2.push(root2)
      root2 = root2.left
    }

    if (stack1[stack1.length - 1].val > stack2[stack2.length - 1].val) {
      root2 = stack2.pop()
      res.push(root2.val)
      root2 = root2.right
    } else {
      root1 = stack1.pop()
      res.push(root1.val)
      root1 = root1.right
    }
  }
  addItem(root1, stack1, res)
  addItem(root2, stack2, res)
  return res
};

function addItem(node: TreeNode, stack: TreeNode[], rs: number[]) {
  while(node !== null || stack.length > 0) {
    while(node !== null) {
      stack.push(node)
      node = node.left
    }
    node = stack.pop()
    rs.push(node.val)
    node = node.right
  }
}