面试题精解之一： 二叉树
本篇文章发表在下面三个博客中，如果出现排版问题，请移步到另一个博客。
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;}
}
}