王道数据结构编程题 查找

二叉树定义

以下为本文解题代码的二叉树定义。

struct TreeNode {int val;TreeNode* left, *right;TreeNode(int val = 0, TreeNode* left = nullptr, TreeNode* right = nullptr): val(val), left(left), right(right) {}
};

递归二分查找

题目描述

写出二分查找的递归算法。初始调用时，left 为1，right 为 n.

解题代码

bool recurBS(vector<int>& 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(vector<int>& 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);
}pair<int, 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);
}