面试题精解之一: 二叉树
本篇文章发表在下面三个博客中,如果出现排版问题,请移步到另一个博客。
http://www.cppblog.com/flyinghearts
http://www.cnblogs.com/flyinghearts
http://blog.csdn.net/flyinghearts
1 求二叉树中相距最远的两个节点之间的距离
2 判断二叉树是否平衡二叉树
3 指定二叉树,给定两节点求其最近共同父节点
4 二叉树的广度遍历、逐层打印二叉树节点数据、只打印某层节点数据
5 在二叉树中找出和(叶子到根节点路径上的所有节点的数据和)为指定值的所有路径。
6 将二叉查找树转为有序的双链表
7 求二叉树的镜像
8 二叉树前序、中序、后序遍历的非递归实现
9 计算二叉树高度的非递归实现
10 连接二叉树同一层上的结点
特别说明:
本文中二叉树结构定义为:
struct Node {
Node* left;
Node* right;
int data;
};
定义:空二叉树的高度为-1,只有根节点的二叉树高度为0,根节点在0层,深度为0。
1 求二叉树中相距最远的两个节点之间的距离
两个节点的距离为两个节点间最短路径的长度。
求两节点的最远距离,实际就是求二叉树的直径。假设相距最远的两个节点分别为A、B,它们的最近共同父节点(允许一个节点是其自身的父节点)为C,则A到B的距离 = A到C的距离 + B到C的距离。
节点A、B分别在C的左右子树下(假设节点C的左右两子树均包括节点C),不妨假设A在C的左子树上,由假设“A到B的距离最大”,先固定B点不动(即B到C的距离不变),根据上面的公式,可得A到C的距离最大,即点A是C左子树下距离C最远的点,即:
A到C的距离 = C的左子树的高度。
同理, B到C的距离 = C的右子树的高度。
因此,本问题可以转化为:“二叉树每个节点的左右子树高度和的最大值”。
static int tree_height(const Node* root, int& max_distance)
{
const int left_height = root->left ? tree_height(root->left, max_distance) + 1 : 0;
const int right_height = root->right ? tree_height(root->right, max_distance) + 1 : 0;
const int distance = left_height + right_height;
if (max_distance < distance) max_distance = distance;
return (left_height > right_height ? left_height : right_height);
}
int tree_diameter(const Node* root)
{
int max_distance = 0;
if (root) tree_height(root, max_distance);
return max_distance;
}
2 判断二叉树是否平衡二叉树
根据平衡二叉树的定义:每个结点的左右子树的高度差小等于1,只须在计算二叉树高度时,同时判断左右子树的高度差即可。
static int tree_height(const Node* root, bool& balanced)
{
const int left_height = root->left ? tree_height(root->left, balanced) + 1 : 0;
if (!balanced) return 0;
const int right_height = root->right ? tree_height(root->right, balanced) + 1 : 0;
if (!balanced) return 0;
const int diff = left_height - right_height;
if (diff < -1 || diff > 1) balanced = false;
return (left_height > right_height ? left_height : right_height);
}
bool is_balanced_tree(const Node* root)
{
bool balanced = true;
if (root) tree_height(root, balanced);
return balanced;
}
3 指定二叉树,给定两节点求其最近共同父节点
遍历二叉树时,只有先访问给定两节点A、B后,才可能确定其最近共同父节点C,因而采用后序遍历。
可以统计任一节点的左右子树“是否包含A、B中的某一个”(也可以直接统计“包含了几个A、B”)。当后序遍历访问到某个节点D时,可得到三条信息:节点D是否是A、B两节点之一、其左子树是否包含A、B两节点之一、其右子树是否包含A、B两节点之一。当三条信息中有两个为真时,就可以确定节点D的父节点(或节点D,如果允许一个节点是自身的父节点的话)就是节点A、B的最近共同父节点。另外,找到最近共同父节点C后应停止遍历其它节点。
① 允许节点是其自身的父节点(若B是A的孩子,A、B的最近共同父节点为A):
//代码1:
static bool lca(const Node* root, const Node* va, const Node* vb, const Node*& result)
{
const bool left = root->left ? lca(root->left, va, vb, result) : false;
if (result) return false; //剪枝,随便返回一个值
const bool right = root->right ? lca(root->right, va, vb, result) : false;
if (result) return false;
//由于va可能等于vb,不要写成: const int mid = (root == va) | (root == vb);
const int mid = (root == va) + (root == vb);
int ret = left + right + mid;
if (ret == 2) result = root;
return (bool)ret;
}
const Node* lca(const Node* root, const Node* va, const Node* vb)
{
const Node* result = NULL;
if (root) lca(root, va, vb, result);
return result;
}
上面的代码中需要特别注意的是:判断所访问时节点是否是两节点A、B时要写成
const int mid = (root == va) + (root == vb);
而不是: const int mid = (root == va) | (root == vb);
这样当va等于vb时,可以得到正确结果。
若采用第二种方法,代码可以改写为:
//代码2:
static int lca(const Node* root, const Node* va, const Node* vb, const Node*& result)
{
const int N = 2;
const int left = root->left ? lca(root->left, va, vb, result) : 0;
if (left == N) return N;
const int right = root->right ? lca(root->right, va, vb, result) : 0;
if (right == N) return N;
const int mid = (root == va) + (root == vb);
const int ret = left + right + mid;
if (ret == N) result = root;
return ret;
}
const Node* lca(const Node* root, const Node* va, const Node* vb)
{
const Node* result = NULL;
if (root) lca(root, va, vb, result);
return result;
}
② 节点不能是其自身的父节点(若B是A的孩子,A、B的最近共同父节点为A的父节点):
只要再增加一个变量保存父节点即可。
static bool lca(const Node* root, const Node* va, const Node* vb,
const Node* parrent, const Node*& result)
{
bool left = false;
if (root->left) {
left = lca(root->left, va, vb, root, result);
if (result) return false;
}
bool right = false;
if (root->right) {
right = lca(root-> right, va, vb, root, result);
if (result) return false;
}
const int mid = (root == va) + (root == vb);
const int ret = left + right + mid;
if (ret == 2) result = (mid != 0 ? parrent : root);
return (bool)ret;
}
const Node* lca(const Node* root, const Node* va, const Node* vb)
{
const Node* result = NULL;
if (root) lca(root, va, vb, NULL, result);
return result;
}
4 二叉树的广度遍历、逐层打印二叉树节点数据、只打印某层节点数据
广度遍历可以用一个队列保存中间结果。每访问一个节点时,将不为空的的左右孩子分别放入队列中,然后从队列头部取出下一个节点,重复前面的操作直到队列为空。
若需要对同一层的节点数据进行一些特殊操作(比如:打印完一层后换行、只打印某一层),可以记录某一层的最后一个节点,当遍历完该节点时(此时,队列的中的最后一个元素恰好就是下一层的最后一个节点),再进行这些特殊操作。
//简单的广度遍历
void bfs(const Node* root)
{
if (root == NULL) return;
std::deque<const Node*> dq;
while (true) {
if (root->left) dq.push_back(root->left);
if (root->right) dq.push_back(root->right);
std::cout << root->data << " ";
if (dq.empty()) break;
root = dq.front();
dq.pop_front();
}
}
//逐层打印
void bfs_level(const Node* root)
{
if (root == NULL) return;
std::deque<const Node*> dq;
const Node* end = root;
while (true) {
if (root->left) dq.push_back(root->left);
if (root->right) dq.push_back(root->right);
std::cout << root->data;
if (root != end) { std::cout << " "; }
else {
std::cout << "\n";
if (dq.empty()) break;
end = dq.back();
}
root = dq.front();
dq.pop_front();
}
}
//只打印某层
void bfs_nth_level(const Node* root, int level) //root node is at level 0
{
if (root == NULL || level < 0) return;
std::deque<const Node*> dq;
const Node* end = root;
while (true) {
if (root->left) dq.push_back(root->left);
if (root->right) dq.push_back(root->right);
if (level == 0) std::cout << root->data << (root == end ? "\n" : " ");
if (root == end) {
if (--level < 0 || dq.empty()) break;
end = dq.back();
}
root = dq.front();
dq.pop_front();
}
}
5 在二叉树中找出和(叶子到根节点路径上的所有节点的数据和)为指定值的所有路径。
要输出所有的路径,必须额外用一个栈来保存当前路径信息。
当访问到节点A时,节点A的信息要在访问A的左右子树时用到,因而,该信息必须在遍历A的左右子树前加入到栈中,而在遍历完A的左右子树后从栈中移除。
每访问一个节点,就计算当前路径值(可直接利用父节点的路径值),当其等于给定值且当前节点是叶子节点时,就打印路径信息。
static void node_path(const Node* root, const int value, int sum, std::deque<int>& dq)
{
sum += root->data;
if (root->left == NULL && root->right == NULL) {
if (sum != value) return;
std::copy(dq.begin(), dq.end(), std::ostream_iterator<int>(std::cout, " "));
std::cout << root->data << "\n";
return;
}
dq.push_back(root->data);
if (root->left) node_path(root->left, value, sum, dq);
if (root->right) node_path(root->right, value, sum, dq);
dq.pop_back();
}
void print_node_path(const Node *root, int value)
{
if (root == NULL) return;
std::deque<int> dq;
node_path(root, value, 0, dq);
}
//非递归解法
void print_path_by_value(const Node *root, int value)
{
typedef std::vector<const Node*> Container;
Container node;
node.reserve(64);
int sum = 0;
while (true) {
for ( ; root != NULL; root = root->left) {
sum += root->data;
if (sum == value && root->left == NULL && root->right == NULL) {
Container::const_iterator first = node.begin(), last = node.end();
for ( ; first != last; ++first) printf("%d ", (*first)->data);
printf("%d\n", root->data);
sum -= root->data;
break;
}
node.push_back(root);
}
while (true) {
if (node.empty()) return;
const Node* parrent = node.back();
if (root != parrent->right) { root = parrent->right; break; }
root = parrent;
sum -= root->data;
node.pop_back();
}
}
}
6 将二叉查找树转为有序的双链表
实际上就是对二叉查找树进行中序遍历。可以用两个变量分别保存刚访问的结点、新链表的头结点,访问某一个结点A时,设置该节点时left成员指向刚访问过的结点B,再设置结点B的right成员指向结点A。经过这样处理,得到的新双链表,除了头结点的left成员、尾结点的right成员没有设置外,其它的结点成员都被正确设置。而中序遍历的特点决定了第一个访问的数据节点的left成员一定为空指针,最后一个访问的数据节点的right成员也一定为空指针。因而不需要再对这两个成员进行额外的设置操作。
static void tree2list_inorder(Node* root, Node*& prev, Node*& list_head)
{
if (root->left) tree2list_inorder(root->left, prev, list_head);
root->left = prev;
if (prev) prev->right = root;
prev = root;
if (list_head == NULL) list_head = root;
if (root->right) tree2list_inorder(root->right, prev, list_head);
}
Node* tree2list(Node* root)
{
Node* list_head = NULL;
Node* prev = NULL;
if (root) tree2list_inorder(root, prev, list_head);
return list_head;
}
7 求二叉树的镜像
① 在原来的二叉树上进行修改。
static void mirror(Node* root)
{
Node* const left = root->left;
Node* const right = root->right;
root->left = right;
root->right = left;
if (left) mirror(left);
if (right) mirror(right);
}
Node* mirror_node(Node* root)
{
if (root) mirror(root);
return root;
}
② 创建一个二叉树的镜像,注意内存分配失败时的处理。
static void clear_node(Node* root)
{
Node* const left = root->left;
Node* const right = root->right;
delete root;
if (left) clear_node(left);
if (right) clear_node(right);
}
static void clone_mirror(const Node* root, Node*& position)
{
Node *node = new Node;
*node = *root;
position = node;
if (root->left) clone_mirror(root->left, node->right);
if (root->right) clone_mirror(root->right, node->left);
}
Node* clone_mirror(const Node* root)
{
Node* new_root = NULL;
if (root) {
try {
clone_mirror(root, new_root);
} catch (...) {
if (new_root) clear_node(new_root);
new_root = NULL;
}
}
return new_root;
}
8 二叉树前序、中序、后序遍历的非递归实现
三种遍历相同点是:从某节点出发向左走到头(边走边记录访问过的节点),然后退回到该节点,再进入右子树,再重复前面操作。
① 对前序遍历,先访问节点数据、以后再访问该节点右孩子的数据,因而可以不记录该节点,而直接记录该节点的右孩子。
② 对前序、中序遍历,同一个节点可能要被访问两次:从上往下、(沿着左子树)从下往上。
③ 对后序遍历,同一个节点可能要被访问三次:从上往下、(沿着左子树)从下往上、(沿着右子树)从下往上。
后序遍历相对麻烦的地方是:从下往上时,要判断是沿着左子树向上,还是沿着右子树向上,若是后者(或父节点的右孩子为空节点)才访问父节点数据。方向的判断,只须判断当前节点是否是其父节点的右孩子,不需要对每个结点都设一个标志!另外,若当前节点是某个叶子节点的左孩子(此时当前节点是空节点),可以把当前节点当作是该叶子节点的右孩子处理,而不影响结果。
void preorder(const Node* root)
{
std::deque<const Node*> dq;
while (true) {
while (root) {
std::cout << root->data << " ";
if (root->right) dq.push_back(root->right);
root = root->left;
}
if (dq.empty()) break;
root = dq.back();
dq.pop_back();
}
}
void inorder(const Node* root)
{
std::deque<const Node*> dq;
while (true) {
for ( ; root != NULL; root = root->left) dq.push_back(root);
if (dq.empty()) break;
root = dq.back();
dq.pop_back();
std::cout << root->data << " ";
root = root->right;
}
}
void postorder(const Node* root)
{
std::deque<const Node*> dq;
while (true) {
for ( ; root != NULL; root = root->left) dq.push_back(root);
while (true) {
if (dq.empty()) return;
const Node* parrent = dq.back();
//可以不检查parrent->right是否为空指针
const Node* right = parrent->right;
if (right && root != right) { root = right; break;}
std::cout << parrent->data << " ";
root = parrent;
dq.pop_back();
}
}
}
9 计算二叉树高度的非递归实现
计算二叉树的高度,一般都是用后序遍历,先算出左子树的高度,再算出右子树的高度,最后取较大者。但若直接将该算法改成非递归形式是非常麻烦的。考虑到二叉树高度与深度的关系,可以有下面两种方法:
① 先将算法改成前序遍历再改写非递归形式。前序遍历算法:遍历一个节点前,先算出当前节点是在哪一层,层数的最大值就等于二叉树的高度。
② 修改上面提到的后序遍历迭代写法,上面的代码中,所用到辅助栈(或双端队列),其大小达到的最大值减去1 就等于二叉树的高度。因而只须记录在往辅助栈放入元素后(或者在访问结点数据时),辅助栈的栈大小达到的最大值。
int tree_height_preorder(const Node* root)
{
struct Info {
const Node* node;
int level;
};
std::deque<Info> dq;
int level = -1;
int height = -1;
while (true) {
while (root) {
++level;
if (root->right) {
Info info = {root->right, level};
dq.push_back(info);
}
root = root->left;
}
height = max(height, level);
if (dq.empty()) break;
const Info& info = dq.back();
root = info.node;
level = info.level;
dq.pop_back();
}
return height;
}
int tree_height_postorder(const Node* root)
{
std::deque<const Node*> dq;
int height = -1;
while (true) {
for ( ; root != NULL; root = root->left) dq.push_back(root);
height = max(height, (int)dq.size() - 1);
while (true) {
if (dq.empty()) return height;
const Node* parrent = dq.back();
//可以不检查parrent->right是否为空指针
const Node* right = parrent->right;
if (right && root != right) { root = right; break;}
root = parrent;
dq.pop_back();
}
}
}
10 连接二叉树同一层上的结点
若二叉树结构定义为:
struct Node {
Node *left;
Node *right;
Node *right_sibling; //
int data;
};
其中,right_sibling指向同一层上右侧的第一个结点(没有的话则设为空指针)。
要求设置各结点的right_sibling成员(其它成员已经初始化)。
本题可以用递归,也可以使用迭代,两种方法都是时间复杂度O(n),空间复杂度O(1)(递归解法可能会栈溢出)。
递归法:访问一个结点前,事先算出它的right_sibling。访问该结点时,利用该结点的right_sibling指针,算出其左右孩子的right_sibling(找出该结点右侧第一个不是叶子的结点B,结点B的某个孩子,就是该结点某个孩子的right_sibling)。需要特别注意的是:访问二叉树可以采用前序遍历,要先访问右子树,再访问左子树,这样可以保证访问到某个结点,该结点及其右侧的结点的right_sibling指针已被正确设置。
迭代法:访问某一层前,先设置好该层所有节点的right_sibling,访问该层时,利用已经设置好的right_sibling信息,设置下一层节点的right_sibling。
//递归解法:
static void set_sibling(Node* root, Node* sibling)
{
root->right_sibling = sibling;
Node* const left = root->left;
Node* const right = root->right;
if (left == NULL && right == NULL) return;
while (sibling) {
if (sibling->left) { sibling = sibling->left; break;}
if (sibling->right) { sibling = sibling->right; break;}
sibling = sibling->right_sibling;
}
if (right) {
set_sibling(right, sibling);
sibling = right;
}
if (left) set_sibling(left, sibling);
}
void set_sibling(Node* root)
{
if (root) set_sibling(root, NULL);
}
//非递归解法:
void set_right_sibling2(Node* root)
{
if (root == NULL) return;
root->right_sibling = NULL;
Node* level_start = NULL;
while (root) {
Node* const left = root->left;
Node* const right = root->right;
if (level_start == NULL) level_start = (left ? left : right);
Node* right_sibling = NULL;
while (1) {
root = root->right_sibling;
if (root == NULL) { root = level_start; level_start = NULL; break; }
if (root->left) { right_sibling = root->left; break;}
if (root->right) { right_sibling = root->right; break;}
}
if (right) { right->right_sibling = right_sibling; right_sibling = right; }
if (left) { left->right_sibling = right_sibling;}
}
}