网站建设单位有哪些方面,手机版网站建设合同范本,硬件开发文档,电子商务有限公司简介二叉树定义
以下为本文解题代码的二叉树定义。
struct TreeNode {int val;TreeNode* left, *right;TreeNode(int val 0, TreeNode* left nullptr, TreeNode* right nullptr): val(val), left(left), right(right) {}
};递归二分查找
题目描述
写出二分查找的递归算法。初…二叉树定义
以下为本文解题代码的二叉树定义。
struct TreeNode {int val;TreeNode* left, *right;TreeNode(int val 0, TreeNode* left nullptr, TreeNode* right nullptr): val(val), left(left), right(right) {}
};递归二分查找
题目描述
写出二分查找的递归算法。初始调用时left 为1right 为 n.
解题代码
bool recurBS(vectorint nums, int target, int left, int right) {if (left right) return false;int mid (left right) / 2;if (nums[mid] target) return true;else if (nums[mid] target) {return recurBS(nums, target, left, mid - 1);}else {return recurBS(nums, target, mid 1, right);}
}优化顺序查找
题目描述
线性表中各结点的检索概率不等时可用如下策略提高顺序检索的效率若找到指定的结点则将该结点和其前驱节点若存在交换使得经常被检索的结点尽量位于表的前端。试设计在顺序结构和链式结构的线性表上实现上述策略的顺序检索算法。
解题代码
顺序表
bool optimisedSS(vectorint nums, int target) {for (int i 0; i nums.size(); i) {if (nums[i] target) {if (i 0) {swap(nums[i - 1], nums[i]);}return true;}}return false;
}链表
bool optimisedSS(ListNode* head, int target) {if (head nullptr) return false;ListNode* dummy new ListNode(-1, head); // 哨兵结点if (dummy-next-val target) return true;while (dummy-next-next ! nullptr) {if (dummy-next-next-val target) {ListNode* pre dummy;ListNode* node1 dummy-next;ListNode* node2 dummy-next-next;pre-next node2;node1-next node2-next;node2-next node1;return true;}dummy dummy-next;}return false;
}判定二叉搜索树
题目描述
试编写一个算法判断给定的二叉树是否是二叉搜索树。
解题代码
bool dfs(TreeNode* root, int preVal) {if (root nullptr) return true;if (!dfs(root-left, preVal) || root-val preVal) {return false;}preVal root-val;return dfs(root-right, preVal);
}bool isBST(TreeNode* root) {int lastVal INT32_MIN;return dfs(root, lastVal);
}计算某结点层次
题目描述
设计一个算法求出指定结点在给定二叉排序树中的层次。
解题代码
int dfs(TreeNode* root, TreeNode* node, int depth) {if (root nullptr) return 0;if (root-val node-val) {return depth;}else if (root-val node-val) {return dfs(root-right, node, depth 1);}else {return dfs(root-left, node, depth 1);}
}int calNodeDepth(TreeNode* root, TreeNode* node) {return dfs(root, node, 1);
}判定平衡二叉树
题目描述
利用二叉树遍历的遍历的思想编写一个判断二叉树是否是平衡二叉树的算法。
解题代码
O(n^2)
int calDepth(TreeNode* root) {if (root nullptr) return 0;return 1 max(calDepth(root-left), calDepth(root-right));
}bool isBalanced(TreeNode* root) {if (root nullptr) return true;int lDepth calDepth(root-left);int rDepth calDepth(root-right);return abs(lDepth - rDepth) 1 isBalanced(root-left) isBalanced(root-right);
}在每次递归判断左右子树是否平衡时需要重新计算其高度因此引入了大量不必要的计算。而如果某棵树的子树之一已经是非平衡树那么这棵树一定是非平衡树根据该性质可将对平衡的判断改为自底向上进行。以下为自底向上判断平衡的方式可将时间复杂度优化至 O(n).
O(n)
int calDepth(TreeNode* root) {if (root nullptr) return 0;int lDepth calDepth(root-left);int rDepth calDepth(root-right);if (lDepth -1 || rDepth -1 || abs(lDepth - rDepth) 2) {return -1;}return 1 max(lDepth, rDepth);
}bool isBalanced(TreeNode* root) {return calDepth(root) 0;
}二叉搜索树最大和最小结点
题目描述
设计一个算法求出给定二叉搜索树中最小和最大的关键字。
解题代码
int calMaxVal(TreeNode* root) {if (root-right nullptr) return root-val;return calMaxVal(root-right);
}int calMinVal(TreeNode* root) {if (root-left nullptr) return root-val;return calMinVal(root-left);
}pairint, int calMaxMin(TreeNode* root) {int minVal root-left nullptr ? root-val : calMinVal(root-left);int maxVal root-right nullptr ? root-val : calMaxVal(root-right);return make_pair(minVal, maxVal);
}二叉搜索树值不小于 k 的元素
题目描述
设计一个算法从大到小输出二叉搜索树中所有值不小于 k 的元素。
解题代码
void printNotSmallerK(TreeNode* root, int k) {if (root nullptr) return;printNotSmallerK(root-right, k);if (root-val k) {cout root-val ;}else return;printNotSmallerK(root-left, k);
}查找第k小的元素
题目描述
编写一个递归算法在一棵有 n 个结点的随机建立起来的二叉搜索树上查找第 k 1 k n小的元素并返回指向该结点的指针要求算法的平均时间复杂度为 O(logn)。二叉搜索树中的每个结点除 data, lchild, rchild 等数据成员外增加一个 count 成员保存以该结点为根的子树上的结点个数。
解题代码
TreeNode* findKthNode(TreeNode* root, int k) {if (root nullptr) return nullptr;TreeNode* left findKthNode(root-left, k);if (left ! nullptr) return left;if (--k 0) return root;return findKthNode(root-right, k);
}
