鱼C论坛

 找回密码
 立即注册
查看: 2132|回复: 0

[技术交流] C++刷LeetCode(1008. 先序遍历构造二叉树)【树】【深度优先搜索】

[复制链接]
发表于 2020-7-18 11:46:44 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
题目描述:

  1. 返回与给定先序遍历 preorder 相匹配的二叉搜索树(binary search tree)的根结点。

  2. (回想一下,二叉搜索树是二叉树的一种,其每个节点都满足以下规则,对于 node.left 的任何后代,值总 < node.val,而 node.right 的任何后代,值总 > node.val。此外,先序遍历首先显示节点的值,然后遍历 node.left,接着遍历 node.right。)



  3. 示例:

  4. 输入:[8,5,1,7,10,12]
  5. 输出:[8,5,10,1,7,null,12]



  6. 提示:

  7. 1 <= preorder.length <= 100
  8. 先序 preorder 中的值是不同的。
复制代码


  1. /**
  2. * Definition for a binary tree node.
  3. * struct TreeNode {
  4. *     int val;
  5. *     TreeNode *left;
  6. *     TreeNode *right;
  7. *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  8. *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  9. *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  10. * };
  11. */
  12. class Solution {
  13. public:
  14.     void dfs(TreeNode* root, int val){
  15.         if(val > root -> val){
  16.             if(root -> right == NULL)root -> right = new TreeNode(val);
  17.             else dfs(root -> right, val);
  18.         }else{
  19.             if(root -> left == NULL)root -> left = new TreeNode(val);
  20.             else dfs(root -> left, val);
  21.         }
  22.     }
  23.     TreeNode* bstFromPreorder(vector<int>& preorder) {
  24.         if(preorder.size() == 0)return NULL;
  25.         TreeNode* root = new TreeNode(preorder[0]);
  26.         for(int i = 1; i < preorder.size(); i++){
  27.             dfs(root, preorder[i]);
  28.         }
  29.         return root;
  30.     }
  31. };
复制代码

本帖被以下淘专辑推荐:

小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2025-7-3 23:39

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表