1305. 两棵二叉搜索树中的所有元素(中序遍历)

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

示例 1：

输入：root1 = [2,1,4], root2 = [1,0,3] 输出：[0,1,1,2,3,4] 示例 2：

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

提示：

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

自己的做法： 二叉搜索树那么直接中序遍历便会得到一个顺序的结果，可以先把顺序的结果暂存下来，然后这个问题变成了合并两个有序数组的问题，直接双指针结束。

中序遍历的递归代码如下：

会把结果存在ans列表里

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

    }

总体代码如下：

class Solution {
          
   
    public List<Integer> getAllElements(TreeNode root1, TreeNode root2) {
          
   
        List<Integer> ans1 = new ArrayList<Integer>();
        List<Integer> ans2 = new ArrayList<Integer>();
        List<Integer> ans = new ArrayList<Integer>();
        Inorder(root1,ans1);
        Inorder(root2,ans2);

        int n = ans1.size();
        int m = ans2.size();
        int i = 0 , j = 0;
        while (i < n && j < m)
        {
          
   
            if(ans1.get(i) < ans2.get(j))
            {
          
   
                ans.add(ans1.get(i));
                i++;
            }
            else
            {
          
   
                ans.add(ans2.get(j));
                j++;
            }
        }
        while ( i < n)
        {
          
   
            ans.add(ans1.get(i));
            i++;
        }
        while (j < m)
        {
          
   
            ans.add(ans2.get(j));
            j++;
        }
        return ans;
    }

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

    }
}