首页 > 代码库 > leetcode --binary tree
leetcode --binary tree
1. 求深度：
recursive 遍历左右子树，递归跳出时每次加一。
int maxDepth(node * root){ if(roor==NULL) return 0; int leftdepth=maxDepth(root->leftchild); int rightdepth=maxDepth(root->rightchild); if(leftdepth>=rightdepth) return leftdepth+1; else return rightdepth+1; }
2. 广度搜索
使用队列
class Solution {public: vector<vector<int>> levelOrderBottom(TreeNode* root) { vector<vector<int>> result; if(!root) return result; int i=0; queue<TreeNode *> q; q.push(root); while(!q.empty()) { int c=q.size(); vector <int> t; for(int i=0;i<c;i++) { TreeNode *temp; temp=q.front(); q.pop(); t.push_back(temp->val); if(temp->left) q.push(temp->left); if(temp->right) q.push(temp->right); } result.push_back(t); } reverse(result.begin(),result.end()); return result; }};3. 二叉查找树
由于二叉查找树是递归定义的，插入结点的过程是：若原二叉查找树为空，则直接插入；否则，若关键字 k 小于根结点关键字，则插入到左子树中，若关键字 k 大于根结点关键字，则插入到右子树中。
/** * 插入：将关键字k插入到二叉查找树 */int BST_Insert(BSTree &T, int k, Node* parent=NULL){ if(T == NULL) { T = (BSTree)malloc(sizeof(Node)); T->key = k; T->left = NULL; T->right = NULL; T->parent = parent; return 1; // 返回1表示成功 } else if(k == T->key) return 0; // 树中存在相同关键字 else if(k < T->key) return BST_Insert(T->left, k, T); else return BST_Insert(T->right, k, T);}构造二叉查找树：
/** * 构造：用数组arr[]创建二叉查找树 */void Create_BST(BSTree &T, int arr[], int n){ T = NULL; // 初始时为空树 for(int i=0; i<n; ++i) BST_Insert(T, arr[i]);}构造平衡二叉查找树：
每次找中间值插入：
class Solution {public: int insertTree(TreeNode * & tree, int a) { if(!tree) { // cout<<a<<endl; tree=new TreeNode(a); tree->left=NULL; tree->right=NULL; return 0; } if(a<tree->val) { return insertTree(tree->left,a); } else return insertTree(tree->right,a); } int createBST(vector<int> &nums, int i,int j,TreeNode* &t) { if(i<=j&&j<nums.size()) { int mid=i+(j-i)/2; cout<<mid<<" "<<nums[mid]<<endl; insertTree(t,nums[mid]); createBST(nums,i,mid-1,t); createBST(nums,mid+1,j,t); } return 0; } TreeNode* sortedArrayToBST(vector<int>& nums) { if(nums.size()==0) return NULL; TreeNode *r=NULL; createBST(nums,0,nums.size()-1,r); /* int i,j; for(i=0, j=nums.size()-1;i<=mid-1 && j>=mid+1;) { cout<<i<<" "<<j<<endl; insertTree(r,nums[i]); i++; insertTree(r,nums[j]); j--; } if(i!=j) { if(i==mid-1) { cout<<nums[i]<<endl; insertTree(r,nums[i]); } if(j==0) { cout<<nums[j]<<endl; insertTree(r,nums[j]); } }*/ return r; }};不好，相当于每次从头遍历一次树， 没有必要。因为小的中间值直接插左边，大的中间值直接插右边
class Solution {private: TreeNode* helper(vector<int>& nums,int start,int end){ if(end<=start){ return NULL; } int mid = start + (end-start)/2; TreeNode* root = new TreeNode(nums[mid]); root->left = helper(nums,start,mid); root->right = helper(nums,mid+1,end); return root; }public: TreeNode* sortedArrayToBST(vector<int>& nums) { return helper(nums,0,nums.size()); }};
leetcode --binary tree
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。