Formatted question description: https://leetcode.ca/all/1305.html

1305. All Elements in Two Binary Search Trees (Medium)

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 = [0,-10,10], root2 = [5,1,7,0,2]
Output: [-10,0,0,1,2,5,7,10]

Example 3:

Input: root1 = [], root2 = [5,1,7,0,2]
Output: [0,1,2,5,7]

Example 4:

Input: root1 = [0,-10,10], root2 = []
Output: [-10,0,10]

Example 5:

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

Constraints:

Each tree has at most 5000 nodes.
Each node's value is between [-10^5, 10^5].

Related Topics:
Sort, Tree

Solution 1.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Integer> getAllElements(TreeNode root1, TreeNode root2) {
        List<Integer> elements1 = inorderTraversal(root1);
        List<Integer> elements2 = inorderTraversal(root2);
        List<Integer> allElements = new ArrayList<Integer>();
        int size1 = elements1.size(), size2 = elements2.size();
        int index1 = 0, index2 = 0;
        while (index1 < size1 && index2 < size2) {
            int element1 = elements1.get(index1), element2 = elements2.get(index2);
            if (element1 <= element2) {
                allElements.add(element1);
                index1++;
            } else {
                allElements.add(element2);
                index2++;
            }
        }
        while (index1 < size1) {
            int element1 = elements1.get(index1);
            allElements.add(element1);
            index1++;
        }
        while (index2 < size2) {
            int element2 = elements2.get(index2);
            allElements.add(element2);
            index2++;
        }
        return allElements;
    }

    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> inorderTraversal = new ArrayList<Integer>();
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode node = root;
        while (!stack.isEmpty() || node != null) {
            while (node != null) {
                stack.push(node);
                node = node.left;
            }
            TreeNode visitNode = stack.pop();
            inorderTraversal.add(visitNode.val);
            node = visitNode.right;
        }
        return inorderTraversal;
    }
}

############

/**
 * 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;
    }
}

// OJ: https://leetcode.com/problems/all-elements-in-two-binary-search-trees/
// Time: O(A + B)
// Space: O(HA + HB)
class BstIterator {
    stack<TreeNode*> s;
    void pushNodes(TreeNode *node) {
        for (; node; node = node->left) s.push(node);
    }
public:
    BstIterator(TreeNode *root) {
        pushNodes(root);
    }
    int peek() {
        return hasNext() ? s.top()->val : INT_MIN;
    }
    bool hasNext() {
        return s.size();
    }
    void next() {
        if (!hasNext()) return;
        auto n = s.top();
        s.pop();
        pushNodes(n->right);
    }
};
class Solution {
public:
    vector<int> getAllElements(TreeNode* a, TreeNode* b) {
        BstIterator i(a), j(b);
        vector<int> ans;
        while (i.hasNext() || j.hasNext()) {
            if (!j.hasNext() || (i.hasNext() && i.peek() <= j.peek())) {
                ans.push_back(i.peek());
                i.next();
            } else {
                ans.push_back(j.peek());
                j.next();
            }
        }
        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.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def getAllElements(self, root1, root2):
        """
        :type root1: TreeNode
        :type root2: TreeNode
        :rtype: List[int]
        """
        nums1 = []
        nums2 = []
        self.inOrder(root1, nums1)
        self.inOrder(root2, nums2)
        return self.merge(nums1, nums2)
        
        
    def inOrder(self, root, nums):
        if not root:
            return
        self.inOrder(root.left, nums)
        nums.append(root.val)
        self.inOrder(root.right, nums)
    
    def merge(self, nums1, nums2):
        res = []
        p1 = 0
        p2 = 0
        while p1 < len(nums1) and p2 < len(nums2):
            if nums1[p1] < nums2[p2]:
                res.append(nums1[p1])
                p1 += 1
            else:
                res.append(nums2[p2])
                p2 += 1
        if p1 < len(nums1):
            res.extend(nums1[p1:])
        if p2 < len(nums2):
            res.extend(nums2[p2:])
        return res

/**
 * 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
    }
}

1305 - All Elements in Two Binary Search Trees

1305. All Elements in Two Binary Search Trees (Medium)

Solution 1.

All Problems

All Solutions

Welcome to Subscribe On Youtube

1305. All Elements in Two Binary Search Trees (Medium)

Solution 1.

All Problems

All Solutions