首页 > 试题广场 >

以下函数用于将一颗二叉搜索树转换成一个有序的双向链表。要求不

[问答题]

以下函数用于将一颗二叉搜索树转换成一个有序的双向链表。要求不能创建任何新的节点,只能调整树种节点指针的指向。

如输入下图中左边的二叉搜索树,则输出转换后的排序双向链表:

      10

    /      \

   6      14

  /  \      /  \

4   8  12  16

转换成:

 4 <=> 6 <=> 8 <=> 10 <=> 12  <=> 14 <=> 16

 

请指出程序代码中错误的地方(问题不止一处,请尽量找出所有你认为错误的地方):

1  #include <stack>

2  using namespace std;

3

4  struct TreeNode {

5        int val;  

6        TreeNode *left, *right;  

7  };

8

9  TreeNode* Convert(TreeNode* root){  

10         if (root == NULL)  

11             return root;

12

13         TreeNode* listHead = NULL;

14         TreeNode* listLastNode = NULL;

15

16         stack<TreeNode*> s;

17         while(root){

18             while(root){

19                 root=root->left;

20                 s.push(root);

21             }

22             root=s.top();  

23             s.pop();

24             if (listHead == NULL){

25                 listHead = root;

26             }else{

27                 listLastNode->right = root;

28             }

29             listLastNode = root;

30             root= root->right;

31         }

32         return listHead;

33 }

#include <stack>

using namespace std;

struct TreeNode {

        int val;  

        TreeNode *left, *right;  

};

TreeNode* Convert(TreeNode* root)
{
    if (root == NULL)
        return root;
    TreeNode* listHead = NULL;
    TreeNode* listLastNode = NULL;
    stack<TreeNode*> s;
+  while(root||s.empty()==0)
    {
        while(root)
        {
+          s.push(root);
            root=root->left;
-           s.push(root);
        }
        root=s.top();
        s.pop();
        if (listHead == NULL)
        {
            listHead = root;
+          listLastNode = listHead;
        }
        else
        {
            listLastNode->right = root;
+          root->left = listLastNode;
+          listLastNode = listLastNode->right;
        }
-       listLastNode = root;
        root= root->right;
    }
    return listHead;
}

发表于 2019-07-12 18:55:38 回复(0)
第17行,应该改成while(s or root):;
第25行,后面应该增加一句 listLastNode = listHead;
第27行后面应该增加
prenode = ListLastNode
ListLastNode = ListLastNode.right
ListLastNode.left = prenode
第29行,应该删除。



发表于 2018-08-07 21:13:07 回复(0)
17  while(s.empty() or root)

19 s.push(root)
20  root = root->left

#插入27行后
root->left = listLastNode   

30行 加入判断语句
if(root->right)
    root = root->right
发表于 2020-01-06 19:45:09 回复(0)