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

前言题目源码

前言

今天是两个二叉搜索树的排序问题，两个思路，一种是将树的所有元素放到列表再排序，一种利用二叉搜索树的性质，使用中序遍历再归并排序

题目

官方题目

源码

中序+归并

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public void dfs(TreeNode node,List<Integer> ans){ if (node==null){ return; } dfs(node.left,ans); ans.add(node.val); dfs(node.right,ans); } public List<Integer> merge(List<Integer> l1,List<Integer>l2){ int size1=l1.size(),size2=l2.size(),i=0,j=0; List<Integer>ans=new ArrayList<>(); while(i<size1 &&j<size2){ int num1=l1.get(i); int num2=l2.get(j); if(num1<num2){ ans.add(num1); i++; }else{ ans.add(num2); j++; } } while(i<size1){ ans.add(l1.get(i++)); } while(j<size2){ ans.add(l2.get(j++)); } return ans; } public List<Integer> getAllElements(TreeNode root1, TreeNode root2) { List<Integer> res1=new ArrayList<>(); List<Integer> res2=new ArrayList<>(); dfs(root1,res1); dfs(root2,res2); return merge(res1,res2); } }

直接取数的所有元素再排序

/** * 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> ans; public void dfs(TreeNode node){ if (node==null){ return; } ans.add(node.val); dfs(node.left); dfs(node.right); } public List<Integer> getAllElements(TreeNode root1, TreeNode root2) { ans=new ArrayList<>(); dfs(root1); dfs(root2); Collections.sort(ans); return ans; } }