Welcome to Subscribe On Youtube
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
-
/** * 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. # 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. * 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 } }