1305两颗二叉搜索树中的所有元素
- 题目链接：https://leetcode-cn.com/problems/all-elements-in-two-binary-search-trees/
- 思路： 知识点：中序遍历：先遍历左节点，在遍历根节点，最后遍历右节点 知识点：二叉搜索树： 当前结点的左子树的树小于当前节点数 当前节点的右子树的树大于当前节点数 左子树右子树自身也是二叉搜索树 将两棵树进行中序遍历，两棵树的数组就都是从大到小有序的 再将两个数组的结点进行比较加入答案数组
- 代码 /** * 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 { void inorder(TreeNode *node, vector<int> &res){ if(node){ inorder(node -> left, res); res.push_back(node -> val); inorder(node -> right, res); } }//中序遍历 public: vector<int> getAllElements(TreeNode* root1, TreeNode* root2) { vector<int> nums1, nums2; inorder(root1, nums1); inorder(root2,nums2); vector<int> merged; auto p1 = nums1.begin(), p2 = nums2.begin(); while(true){ if(p1 == nums1.end()){ merged.insert(merged.end(), p2, nums2.end()); break; } if(p2 == nums2.end()){ merged.insert(merged.end(), p1, nums1.end()); break; } if(*p1 < *p2){ merged.push_back(*p1++); }else{ merged.push_back(*p2++); } } return merged; } };
