Question

1305. All Elements in Two Binary Search Trees

中文文档

Description

Given two binary search trees root1 and root2, return _a list containing all the integers from both trees sorted in ascending order_.

 

Example 1:

Input: root1 = [2,1,4], root2 = [1,0,3]
Output: [0,1,1,2,3,4]

Example 2:

Input: root1 = [1,null,8], root2 = [8,1]
Output: [1,1,8,8]

 

Constraints:

• The number of nodes in each tree is in the range [0, 5000].
• -105 <= Node.val <= 105

Solutions

Solution 1

# Definition for a binary tree node.
# class TreeNode:
#   def __init__(self, val=0, left=None, right=None):
#     self.val = val
#     self.left = left
#     self.right = right
class Solution:
  def getAllElements(self, root1: TreeNode, root2: TreeNode) -> List[int]:
    def dfs(root, t):
      if root is None:
        return
      dfs(root.left, t)
      t.append(root.val)
      dfs(root.right, t)

    def merge(t1, t2):
      ans = []
      i = j = 0
      while i < len(t1) and j < len(t2):
        if t1[i] <= t2[j]:
          ans.append(t1[i])
          i += 1
        else:
          ans.append(t2[j])
          j += 1
      while i < len(t1):
        ans.append(t1[i])
        i += 1
      while j < len(t2):
        ans.append(t2[j])
        j += 1
      return ans

    t1, t2 = [], []
    dfs(root1, t1)
    dfs(root2, t2)
    return merge(t1, t2)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *   int val;
 *   TreeNode left;
 *   TreeNode right;
 *   TreeNode() {}
 *   TreeNode(int val) { this.val = val; }
 *   TreeNode(int val, TreeNode left, TreeNode right) {
 *     this.val = val;
 *     this.left = left;
 *     this.right = right;
 *   }
 * }
 */
class Solution {
  public List<Integer> getAllElements(TreeNode root1, TreeNode root2) {
    List<Integer> t1 = new ArrayList<>();
    List<Integer> t2 = new ArrayList<>();
    dfs(root1, t1);
    dfs(root2, t2);
    return merge(t1, t2);
  }

  private void dfs(TreeNode root, List<Integer> t) {
    if (root == null) {
      return;
    }
    dfs(root.left, t);
    t.add(root.val);
    dfs(root.right, t);
  }

  private List<Integer> merge(List<Integer> t1, List<Integer> t2) {
    List<Integer> ans = new ArrayList<>();
    int i = 0, j = 0;
    while (i < t1.size() && j < t2.size()) {
      if (t1.get(i) <= t2.get(j)) {
        ans.add(t1.get(i++));
      } else {
        ans.add(t2.get(j++));
      }
    }
    while (i < t1.size()) {
      ans.add(t1.get(i++));
    }
    while (j < t2.size()) {
      ans.add(t2.get(j++));
    }
    return ans;
  }
}

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *   int val;
 *   TreeNode *left;
 *   TreeNode *right;
 *   TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *   TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *   TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
  vector<int> getAllElements(TreeNode* root1, TreeNode* root2) {
    vector<int> t1;
    vector<int> t2;
    dfs(root1, t1);
    dfs(root2, t2);
    return merge(t1, t2);
  }

  void dfs(TreeNode* root, vector<int>& t) {
    if (!root) return;
    dfs(root->left, t);
    t.push_back(root->val);
    dfs(root->right, t);
  }

  vector<int> merge(vector<int>& t1, vector<int>& t2) {
    vector<int> ans;
    int i = 0, j = 0;
    while (i < t1.size() && j < t2.size()) {
      if (t1[i] <= t2[j])
        ans.push_back(t1[i++]);
      else
        ans.push_back(t2[j++]);
    }
    while (i < t1.size()) ans.push_back(t1[i++]);
    while (j < t2.size()) ans.push_back(t2[j++]);
    return ans;
  }
};

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *   Val int
 *   Left *TreeNode
 *   Right *TreeNode
 * }
 */
func getAllElements(root1 *TreeNode, root2 *TreeNode) []int {
  var dfs func(root *TreeNode) []int
  dfs = func(root *TreeNode) []int {
    if root == nil {
      return []int{}
    }
    left := dfs(root.Left)
    right := dfs(root.Right)
    left = append(left, root.Val)
    left = append(left, right...)
    return left
  }
  merge := func(t1, t2 []int) []int {
    var ans []int
    i, j := 0, 0
    for i < len(t1) && j < len(t2) {
      if t1[i] <= t2[j] {
        ans = append(ans, t1[i])
        i++
      } else {
        ans = append(ans, t2[j])
        j++
      }
    }
    for i < len(t1) {
      ans = append(ans, t1[i])
      i++
    }
    for j < len(t2) {
      ans = append(ans, t2[j])
      j++
    }
    return ans
  }
  t1, t2 := dfs(root1), dfs(root2)
  return merge(t1, t2)
}

/**
 * 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 = [];
  const stacks = [[], []];
  while (root1 != null || stacks[0].length !== 0 || root2 != null || stacks[1].length !== 0) {
    if (root1 != null) {
      stacks[0].push(root1);
      root1 = root1.left;
    } else if (root2 != null) {
      stacks[1].push(root2);
      root2 = root2.left;
    } else {
      if (
        (stacks[0][stacks[0].length - 1] ?? { val: Infinity }).val <
        (stacks[1][stacks[1].length - 1] ?? { val: Infinity }).val
      ) {
        const { val, right } = stacks[0].pop();
        res.push(val);
        root1 = right;
      } else {
        const { val, right } = stacks[1].pop();
        res.push(val);
        root2 = right;
      }
    }
  }
  return res;
}

// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
//   pub val: i32,
//   pub left: Option<Rc<RefCell<TreeNode>>>,
//   pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
//   #[inline]
//   pub fn new(val: i32) -> Self {
//   TreeNode {
//     val,
//     left: None,
//     right: None
//   }
//   }
// }
use std::cell::RefCell;
use std::rc::Rc;
impl Solution {
  pub fn get_all_elements(
    root1: Option<Rc<RefCell<TreeNode>>>,
    root2: Option<Rc<RefCell<TreeNode>>>
  ) -> Vec<i32> {
    fn dfs(root: &Option<Rc<RefCell<TreeNode>>>, t: &mut Vec<i32>) {
      if let Some(root) = root {
        dfs(&root.borrow().left, t);
        t.push(root.borrow().val);
        dfs(&root.borrow().right, t);
      }
    }

    let mut t1 = Vec::new();
    let mut t2 = Vec::new();
    dfs(&root1, &mut t1);
    dfs(&root2, &mut t2);

    let mut ans = Vec::new();
    let mut i = 0;
    let mut j = 0;
    while i < t1.len() && j < t2.len() {
      if t1[i] < t2[j] {
        ans.push(t1[i]);
        i += 1;
      } else {
        ans.push(t2[j]);
        j += 1;
      }
    }
    while i < t1.len() {
      ans.push(t1[i]);
      i += 1;
    }
    while j < t2.len() {
      ans.push(t2[j]);
      j += 1;
    }
    ans
  }
}