Leecode 108:将有序数组转换成二叉搜索树，传指针或引用对程序的影响

108. 将有序数组转换为二叉搜索树
     给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。

高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

---

下面是一个错误的解法：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
    public:
    void insert(TreeNode*&root ,int val)
    {
        if(root==nullptr){
            root=new TreeNode(val);
        }
        else if(val>root->val)
        {
            insert(root->right,val);
        }
       else  if(val<root->val)
        {
            insert(root->left,val);
        }

    }
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        int root_index=nums.size()/2;
        struct TreeNode* root=new TreeNode(nums[root_index]);
        
        queue<int>tmp;
        for(int i=0;i<nums.size();i++)
        {   
            if(nums[i]==nums[root_index]){continue;}
            tmp.push(nums[i]);
        }
        for(int i=0;i<nums.size()-1;i++){
        insert(root,tmp.front());
        tmp.pop();
        }
        return root;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

我把“平衡”理解成了只有根节点平衡就可以了
但是，如果是0，1,2，3,4，5,6测试用例

最后每一个节点的左右不满足平衡条件。
归根接地，二叉树的构建是递归方式，而考虑平衡时也应该按照递归去约束。

解法1：

也是上面的思路，就是每次得根节点都是nums数组的中间位。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
    public:
    TreeNode* transform_TwoserachTree( TreeNode*&root,int left,int right,vector<int>&nums)
    {   
        if(left>right){return nullptr;}
        int medium=(left+right)/2;
        
            root=new TreeNode(nums[medium]);
        
        
        root->left=transform_TwoserachTree(root->left,left,medium-1,nums);
        root->right=transform_TwoserachTree(root->right,medium+1,right,nums);
        return root;

    }
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        int left=0,right=nums.size()-1;
       
             TreeNode *root= transform_TwoserachTree(root,left,right,nums);
            return root;
    }
     
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

---

下面的写法和上面一样，唯一不一样的就是没传root根节点：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
    public:
    TreeNode* transform_TwoserachTree( int left,int right,vector<int>&nums)
    {   
        if(left>right){return nullptr;}
        int medium=(left+right)/2;
        
             TreeNode*  root=new TreeNode(nums[medium]);
        
        
        root->left=transform_TwoserachTree(left,medium-1,nums);
        root->right=transform_TwoserachTree(medium+1,right,nums);
        return root;

    }
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        int left=0,right=nums.size()-1;
       
            TreeNode *root= transform_TwoserachTree(left,right,nums);
            return root;
    }
     
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

在传参时也可以不以引用传参而传指针，也照样通过测试：为什么？

TreeNode* transform_TwoserachTree(TreeNode* root, int left,int right,vector&nums)

每次new的时候都在一个新的函数体中，构建完之后结构体中的left和right指针就能记住每次new的结构的地址。

以下二叉搜索树不加引用的情况

（插入和删除操作的函数）必须传引用。

class Node
{
public:
	Node(int v) :m_value(v), m_left(NULL), m_right(NULL) {}
	int m_value;
	Node* m_left;
	Node* m_right;
};
class BSTree
{
public:
	BSTree() :m_root(NULL) {}
	void InsertBSTValue(Node*& root, int v);//本案例要把&去掉
	Node* Search(Node* root, int k);
	void Del(Node*& root, int k);  // 删除值为k的结点
	int GetMax()const;
	int GetMin()const;
	void Sort(Node* root);
	Node* m_root;
};
/*
创建二叉树排序树--递归
1.先创建根
2.用v和根比较，vroot，则创建右子树
*/
void BSTree::InsertBSTValue(Node*& root, int v)本案例要把&去掉
{
	if (root == NULL)
	{
		root = new Node(v);
	}
	else if (v < root->m_value)
	{
		InsertBSTValue(root->m_left, v);
	}
	else if (v > root->m_value)
	{
		InsertBSTValue(root->m_right, v);
	}
}
void BSTree::Del(Node*& root, int k)//注意，这里void BSTree::Del(Node* root, int k) 不加引用不正确，改不了root的值。
{                                                              //因为形参中的root只是一个副本，只有指针，不解引用是改不了实参本身的。
	Node* temp = NULL;
	if (root != NULL)
	{
		if (k < root->m_value)
			Del(root->m_left, k);
		else if (k > root->m_value)
			Del(root->m_right, k);
		//找到了要删除的，此结点有左孩子和右孩子 
		else if (root->m_left != NULL && root->m_right != NULL)
		{
			/*
			替换：要么用第一个左孩子的最右侧孩子替换，要么用第一个右孩子的最左侧孩子
			*/
			temp = root->m_right;
			while (temp->m_left != NULL)
				temp = temp->m_left;
			root->m_value = temp->m_value; // 替换
			Del(root->m_right, root->m_value);
		}
		//找到了，要么没有孩子，要么有一个孩子
		else
		{
			temp = root;
			if (root->m_left == NULL)
				root = root->m_right;
			else
				root = root->m_left;
			delete temp;
			temp = NULL;
		}
	}
}
void main()
{
	BSTree bst; // 定义了一颗空树
	int arr[] = { 62,88,58,47,35,73,51,99,37,93 };
	int n = sizeof(arr) / sizeof(arr[0]);
	int i;
	for (i = 0; i < n; ++i)
	{
		bst.InsertBSTValue(bst.m_root, arr[i]);
	}
	cout << "sort : " << endl;
	bst.Sort(bst.m_root);
	cout << endl;
	Node* p = bst.Search(bst.m_root, 62);
	if (p != NULL)
		cout << "p = " << p->m_value << endl;
	else
		cout << "没找到" << endl;
	cout << "min = " << bst.GetMin() << endl;
	cout << "max = " << bst.GetMax() << endl;
	cout << "Del :" << endl;
	bst.Del(bst.m_root, 93);
	bst.Sort(bst.m_root);
	cout << endl;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101

如果不加引用：

因为第一次调动插入函数时是传入的是空指针，构建了对象之后，把对象地址给了root，而函数生存期到 了以后root就跟着被回收了，所以无法构建二叉树。