力扣——1305. 两棵二叉搜索树中的所有元素（Java、JavaScript）

JavaScript代码：

/**
 * @param {TreeNode} root1
 * @param {TreeNode} root2
 * @return {number[]}
 */
var getAllElements = function (root1, root2) {
  function BSTIterator(root) {
    let stack = [];
    // 左侧树枝一撸到底
    const pushLeftBrach = (p) => {
      while (p) {
        stack.push(p);
        p = p.left;
      }
    };
    pushLeftBrach(root);
    this.peek = () => {
      return stack[stack.length - 1].val;
    };
    this.next = () => {
      let p = stack.pop();
      pushLeftBrach(p.right);
      return p.val;
    };
    this.hasNext = () => {
      return stack.length;
    };
  }
  let t1 = new BSTIterator(root1);
  let t2 = new BSTIterator(root2);
  let res = [];
  while (t1.hasNext() && t2.hasNext()) {
    if (t1.peek() > t2.peek()) {
      res.push(t2.next());
    } else {
      res.push(t1.next());
    }
  }
  // 如果有一棵 BST 还剩元素，添加到最后
  while (t1.hasNext()) {
    res.push(t1.next());
  }
  while (t2.hasNext()) {
    res.push(t2.next());
  }
  return res;
};

Java代码：

class Solution {
    public List<Integer> getAllElements(TreeNode root1, TreeNode root2) {
        List<Integer> nums1 = new ArrayList<Integer>();
        List<Integer> nums2 = new ArrayList<Integer>();
        inorder(root1, nums1);
        inorder(root2, nums2);

        List<Integer> merged = new ArrayList<Integer>();
        int p1 = 0, p2 = 0;
        while (true) {
            if (p1 == nums1.size()) {
                merged.addAll(nums2.subList(p2, nums2.size()));
                break;
            }
            if (p2 == nums2.size()) {
                merged.addAll(nums1.subList(p1, nums1.size()));
                break;
            }
            if (nums1.get(p1) < nums2.get(p2)) {
                merged.add(nums1.get(p1++));
            } else {
                merged.add(nums2.get(p2++));
            }
        }
        return merged;
    }

    public void inorder(TreeNode node, List<Integer> res) {
        if (node != null) {
            inorder(node.left, res);
            res.add(node.val);
            inorder(node.right, res);
        }
    }
}

作者：KJ.JK
本文仅用于交流学习，未经作者允许，禁止转载，更勿做其他用途，违者必究。
文章对你有所帮助的话，欢迎给个赞或者 star，你的支持是对作者最大的鼓励，不足之处可以在评论区多多指正，交流学习