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

南鱼座α 213 2022-05-02

题目内容

给你 root1 和 root2 这两棵二叉搜索树。请你返回一个列表,其中包含 两棵树 中的所有整数并按 升序 排序。

示例 1:
image

输入:root1 = [2,1,4], root2 = [1,0,3]
输出:[0,1,1,2,3,4]

示例 2:
image-1651477585401

输入:root1 = [1,null,8], root2 = [8,1]
输出:[1,1,8,8]

提示:

  • 每棵树的节点数在 [0, 5000] 范围内
  • -105 <= Node.val <= 105

解题思路

对两颗二叉搜索树中序遍历,把两个中序遍历结果合并。

public class Solution {

   public List<Integer> getAllElements(TreeNode root1, TreeNode root2) {
       List<Integer> d1 = new ArrayList<>();
       List<Integer> d2 = new ArrayList<>();
       inorderTraversal(root1, d1);
       inorderTraversal(root2, d2);

       List<Integer> list = new ArrayList<>();
       int l1 = d1.size(), l2 = d2.size(), i = 0, j = 0;
       while (i < l1 || j < l2) {
           int a = i < l1 ? d1.get(i) : Integer.MAX_VALUE, b = j < l2 ? d2.get(j) : Integer.MAX_VALUE;

           if (a < b) {
               list.add(a);
               i++;
           } else {
               list.add(b);
               j++;
           }
       }

       return list;
   }

   private void inorderTraversal(TreeNode node, List<Integer> deque) {
       if (node == null) return;
       inorderTraversal(node.left, deque);
       deque.add(node.val);
       inorderTraversal(node.right, deque);
   }
}


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

运行结果

image-1651477877052


# LeetCode # 每日一题 # Medium