雁过无痕

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::

面试题精解之一: 二叉树

 

本篇文章发表在下面三个博客中,如果出现排版问题,请移步到另一个博客。

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;}

 }

}

 

 

posted on 2012-02-28 20:54 flyinghearts 阅读(9451) 评论(3)  编辑 收藏 引用 所属分类: 面试题精解

评论

# re: 面试题精解之一: 二叉树 2012-02-29 09:11 tb
不错的   回复  更多评论
  

# re: 面试题精解之一: 二叉树 2014-07-12 17:48 蘑菇姐
http://www.ssnz88.net/aspcms/news/2014-7-12/681.html  回复  更多评论
  

# re: 面试题精解之一: 二叉树 2014-10-16 14:52 3d
先固定B点不动(即B到C的距离不变),根据上面的公式,可得A到C的距离最大,即点A是C左子树下距离C最远的点,即:  回复  更多评论
  


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理