今日算法(二叉树)

搜索值使用前中后序都可以这里我使用层序遍历进行遍历使用队列进行遍历时间复杂度Onclass Solution { public: TreeNode* searchBST(TreeNode* root, int val) { // TreeNode*nodenew TreeNode(0); //遍历二叉树找到返回 queueTreeNode* que; que.push(root); while(!que.empty()) { TreeNode*nodeque.front(); que.pop(); if(node-valval) return node; if(node-left) que.push(node-left); if(node-right) que.push(node-right); } return nullptr; } };层序遍历称为BFS但这里是暴力搜索TreeNode* searchBST(TreeNode* root, int val) { while(root){ if(root-val val) return root; else if(val root-val) root root-left; else root root-right; } return nullptr; }因为这是二叉搜索树所以直接比较然后找就行时间复杂度为O(logN).下面是递归写法class Solution { public: TreeNdoe*searchBST(TreeNdoe*root,int val) { if(rootnullptr||root-valval) return root; TreeNdoe*resultnullptr; if(root-val val) resultsearchBST(root-left,val); if(root-val val) resultsearchBST(root-right,val); return result; }