devbox
凡人多烦事01
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

C++进阶：搜索树

作者：凡人多烦事01 | 2024-04-21 19:00:19

赞

踩

C++进阶：搜索树

目录

1. 二叉搜索树

1.1 二叉搜索树的结构

  1. 搜索二叉树中的所有结点都满足
    <1> 若左子树不为空，则其所有结点的键值都小于父结点
    <2> 若右子树不为空，则其所有结点的键值都大于父节点
    <3> 左右子树都为二叉搜索树

在这里插入图片描述

1.2 二叉搜索树的接口及其优点与不足

  1. 搜索二叉树的功能接口
    <1> 数据插入（Insert）
    <2> 数据删除（Erase）
    <3> 数据查寻（Find）
    <4> 中序遍历（InOrder）
  1. 二叉搜索树的优点：
    <1> 正如其名，此种数据存储结构，尤其擅长数据搜索，其进行数据搜索的效率极高。
    <2> 在其结构为近似完全二叉树或满二叉树的情况时，其的搜索效率可以达到O( l o g N logN logN)
    <3> 当以中序遍历的方式遍历整棵搜索树时，得到的数据即为升序序列

在这里插入图片描述

  1. 二叉搜索树的不足：
    <1> 根据二叉搜索树的插入逻辑，当数据以完全升序或降序插入时，会使得二叉树退化为单枝结构，此种结构下其搜索效率也退化为O(N)

在这里插入图片描述

1.3 二叉搜索树自实现

1.3.1 二叉树结点结构

  1. 搜索树结点：由左右孩子结点指针与key组成
  2. 搜索树：由根节点与类方法构成
template<class T>
struct BinarySearchNode
{
	typedef BinarySearchNode<T> BSNode;

	BSNode* _left;
	BSNode* _right;
	T _key;

	BinarySearchNode(T key)
		:_left(nullptr)
		,_right(nullptr)
		,_key(key)
	{}
};

template<class T>
class BinarySearchTree
{
public:
	typedef BinarySearchNode<T> BSNode;
	
	//查找
	bool Find(T key);

	//插入
	bool Insert(T key);

	//删除
	bool Erase(T key);

	//中序遍历
	void InOrder();

private:
	BSNode* _root = nullptr;
};

  • 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

1.3.2 查找

  1. 查找实现：在一颗搜索树中搜寻一个数据是否存在
  2. 查找逻辑：
    <1> 若查找值小于当前结点的key值，向左搜寻，向左孩子查找
    <2> 若查找值大于当前结点的key值，向右搜寻，向右孩子查找
    <3> 查找遍历至空结点，则证明搜索树中不存在此值
//非递归
bool Find(T key)
{
	BSNode* cur = _root;

	while (cur)
	{
		if (key < cur->_key)
		{
			cur = cur->_left;
		}
		else if (key > cur->_key)
		{
			cur = cur->_right;
		}
		else
		{
			return true;
		}
	}

	return false;
}

//递归
bool _FindR(BSNode* cur, T key)
{
	if (cur == nullptr)
	{
		return false;
	}

	if (key < cur->_key)
	{
		return _FindR(cur->_left, key);
	}
	else if (key > cur->_key)
	{
		return _FindR(cur->_right, key);
	}
	else
	{
		return true;
	}

	//补全返回路径
	assert(true);
	return -1;
}

bool FindR(T key)
{
	return _FindR(_root, key);
}

  • 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

1.3.3 插入

  1. 搜寻插入位置：
    <1> key小向左
    <2> key大向右
    <3> 直至遍历到空
  2. <1> 若遇key相同的结点，停止插入，返回false
    <2> 遍历至空，创建结点，链接结点
//非递归
bool Insert(T key)
{
	//特殊处理根结点插入
	if (_root == nullptr)
	{
		_root = new BSNode(key);
		return true;
	}

	BSNode* cur = _root;
	BSNode* parent = nullptr;
	while (cur)
	{
		if (key < cur->_key)
		{
			parent = cur;
			cur = cur->_left
		}
		else if (key > cur->_key)
		{
			parent = cur;
			cur = cur->_right;
		}
		else
		{
			return false;
		}
	}

	//确定插入位置
	if (key < parent->_key)
	{
		parent->_left = new BSNode(key);
	}
	else
	{
		parent->_right = new BSNode(key);
	}

	return true;
}

//递归
bool _InsertR(BSNode*& cur, T key)
{
	//存在单子树的情况，导致段错误
	//传引用
	if (cur == nullptr)
	{
		cur = new BSNode(key);

		return true;
	}

	if (key < cur->_key)
	{
		return _InsertR(cur->_left, key);
	}
	else if (key > cur->_key)
	{
		return _InsertR(cur->_right, key);
	}
	else
	{
		return false;
	}

	assert(true);
	return false;
}

bool InsertR(T key)
{
	if (_root == nullptr)
	{
		_root = new BSNode(key);
		
		return true;
	}

	return _InsertR(_root, key);
}

  • 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

1.3.4 删除

  1. 删除结点后，不能破坏搜索树的结构
  2. 删除不同类型结点的场景，删除逻辑：
    <1> 叶子结点，直接删除，父节点链接指针置空
    <2> 单子树结点，托孤，即，将自己的子树链接给父结点
    <3> 双子树结点，寻找key值最接近的结点（左子树的最右结点，右子树的最左结点），值替换被删除的结点，而后删除被替换的结点
  1. 叶子结点
    在这里插入图片描述
  2. 单子树结点
    在这里插入图片描述
  3. 双子树结点
    在这里插入图片描述
//非递归
bool Erase(T key)
{
	BSNode* cur = _root;
	BSNode* parent = nullptr;
	while (cur)
	{
		//查找到删除结点的位置
		if (key < cur->_key)
		{
			parent = cur;
			cur = cur->_left;
		}
		else if (key > cur->_key)
		{
			parent = cur;
			cur = cur->_right;
		}
		else//找到了
		{
			//叶子结点与单子树结点的删除
			//可以合并共用一套逻辑
			if (cur->_left == nullptr || cur->_right == nullptr)//叶子结点/单子树
			{
				//根结点特殊处理
				if (cur == _root)
				{
					if (cur->_left)
					{
						_root = cur->_left;
					}
					else
					{
						_root = cur->_right;
					}

					delete cur;
				}
				else//普通结点
				{
					//托孤
					if (cur->_left)//左单子树
					{
						if (cur == parent->_left)
						{
							parent->_left = cur->_left;
						}
						else
						{
							parent->_right = cur->_left;
						}
						delete cur;
					}
					else//右单子树/叶子节点
					{
						if (cur == parent->_left)
						{
							parent->_left = cur->_right;
						}
						else
						{
							parent->_right = cur->_right;
						}
						delete cur;
					}
				}

				return true;
			}
			else//双子树
			{
				//寻找右子树的最左结点
				BSNode* RightParent = cur;
				BSNode* RightMin = cur->_right;

				while (RightMin->_left)
				{
					RightParent = RightMin;
					RightMin = RightMin->_left;
				}

				//值替换
				cur->_key = RightMin->_key;

				//删除被替换结点
				//删除结点的左孩子一定为空，所以按照右子树结点处理
				//托孤
				if (RightMin == RightParent->_left)
				{
					RightParent->_left = RightMin->_right;
				}
				else
				{
					RightParent->_right = RightMin->_right;
				}

				//删除
				delete RightMin;

				return true;
			}
		}
	}

	//未找到
	return false;
}

//递归
bool _EraseR(BSNode*& cur, T key)
{
	if (cur == nullptr)
	{
		return false;
	}

	//寻找删除结点
	if (key < cur->_key)
	{
		return _EraseR(cur->_left, key);
	}
	else if (key > cur->_key)
	{
		return _EraseR(cur->_right, key);
	}
	else//找到了
	{
		//使用传引用后，对操作的优化
		if (cur->_left == nullptr || cur->_right == nullptr)//叶子结点/单子树结点
		{
			BSNode* del = cur;
			if (cur->_left)
			{
				cur = cur->_left;
			}
			else
			{
				cur = cur->_right;
			}
			delete del;

			return true;
		}
		else//双子树
		{
			//寻找右子树的最左结点
			BSNode* RightMin = cur->_right;
			while (RightMin->_left)
			{
				RightMin = RightMin->_left;
			}

			//值替换
			cur->_key = RightMin->_key;

			//值替换后，删除结点传值改变
			//转化为单子树删除，调用单子树删除处理
			_EraseR(cur->_right, cur->_key);
		}
	}

	assert(true);
	return false;
}

  • 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
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
  • 133
  • 134
  • 135
  • 136
  • 137
  • 138
  • 139
  • 140
  • 141
  • 142
  • 143
  • 144
  • 145
  • 146
  • 147
  • 148
  • 149
  • 150
  • 151
  • 152
  • 153
  • 154
  • 155
  • 156
  • 157
  • 158
  • 159
  • 160
  • 161
  • 162
  • 163
  • 164

1.3.5 中序遍历

void _InOrder(BSNode* cur)
{
	if (cur == nullptr)
	{
		return;
	}

	//左根右
	_InOrder(cur->_left);
	cout << cur->_key << " ";
	_InOrder(cur->_right);
}

void InOrder()
{
	_InOrder(_root);
	cout << endl;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18

2. 二叉树进阶相关练习

2.1 根据二叉树创建字符串

  1. 题目信息：
    在这里插入图片描述
  2. 题目连接：
    根据二叉树创建字符串
class Solution 
{
public:
    void _tree2str(string& str, TreeNode* cur)
    {
        if(cur == nullptr)
        {
            return;
        }
        //字符串转字符串stoi（整形），stod（浮点型）
        str += to_string(cur->val);

        //除左空右不空的情况外，其余省略
        if(cur->left || cur->right)
        {
            str += "(";
            _tree2str(str, cur->left);
            str += ")";
        }

        if(cur->right)
        {
            str += "(";
            _tree2str(str, cur->right);
            str += ")";
        }
    }

    string tree2str(TreeNode* root) 
    {
        string ret;
        //递归
        _tree2str(ret, root);

        return ret;
    }
};

  • 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

2.2 二叉树的层序遍历I

  1. 题目信息：
    在这里插入图片描述
  2. 题目连接：
    二叉树的层序遍历I
  3. 思路：levelsize计数
class Solution
{
public:
    vector<vector<int>> levelOrder(TreeNode* root)
    {
        //levelsize计数
        vector<vector<int>> ret;
        queue<TreeNode*> q;
        int levelsize = 1;
        q.push(root);
        //可能为空树
        if(root == nullptr)
        {
            return ret;
        }

        while (!q.empty())
        {
            vector<int> count;
            while (levelsize--)
            {
                //记录
                TreeNode* top = q.front();
                q.pop();
                count.push_back(top->val);
                //插入新结点
                if (top->left)
                    q.push(top->left);
                if (top->right)
                    q.push(top->right);
            }
            levelsize = q.size();
            ret.push_back(count);
        }

        return ret;
    }
};

  • 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

2.3 二叉树层序遍历II

  1. 题目信息：
    在这里插入图片描述
  2. 题目连接：
    二叉树层序遍历II
  3. 思路：反转自上至下的层序遍历
class Solution 
{
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) 
    {
        //全部压栈，无法判断层
        //得出自上至下的序列，然后逆置
        vector<vector<int>> ret;
        if(root == nullptr)
        {
            return ret;
        }
        queue<TreeNode*> q;
        int levelsize = 1;
        q.push(root);
        while(!q.empty())
        {
            vector<int> count;
            while(levelsize--)
            {
                TreeNode* cur = q.front();
                q.pop();
                count.push_back(cur->val);
                if(cur->left)
                    q.push(cur->left);
                if(cur->right)
                    q.push(cur->right);
            }
            levelsize = q.size();
            ret.push_back(count);
        }

        reverse(ret.begin(), ret.end());

        return ret;
    }
};

  • 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

2.4 二叉树最近公共祖先结点

  1. 题目信息：
    在这里插入图片描述
  2. 二叉树最近公共祖先结点
  3. 思路：
    <1> 方法1：p与q一定分别在祖先结点的左侧与右侧，祖先结点可能是自己
    <2> 方法2：栈记录遍历路径，路径上的所有祖先结点
//方法1：
class Solution 
{
public:
    bool SearchNode(TreeNode* cur, TreeNode* search)
    {
        if(cur == nullptr)
        {
            return false;
        }

        if(cur == search)
        {
            return true;
        }

        return SearchNode(cur->left, search) || SearchNode(cur->right, search);
    }

    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) 
    {
        bool qInleft = false;
        bool qInright = false;
        bool pInleft = false;
        bool pInright = false;
        TreeNode* cur = root;
        while(cur)
        {
            //可能最近祖先结点是自己
            if(cur == p)
            {
                pInleft = pInright = true;
            }
            else if(SearchNode(cur->left, p))
            {
                pInleft = true;
                pInright = false;
            }
            else
            {
                pInright = true;
                pInleft = false;
            }

            if(cur == q)
            {
                qInleft = qInright = true;
            }
            else if(SearchNode(cur->left, q))
            {
                qInleft = true;
                qInright = false;
            }
            else
            {
                qInright = true;
                qInleft = false;
            }

            if((pInleft && qInright) || (pInright && qInleft))
                break;
            else if(pInleft && qInleft)
                cur = cur->left;
            else
                cur = cur->right;
        }

        return cur;
    }
};

//方法2：
class Solution 
{
public:
    bool PreOrder(TreeNode* cur, TreeNode* search, stack<TreeNode*>& count)
    {
        if(cur == nullptr)
        {
            return false;
        }

        count.push(cur);

        if(cur == search)
        {
            return true;
        }

        if(!PreOrder(cur->left, search, count) && !PreOrder(cur->right, search, count))
        {
            count.pop();
        }
        else
        {
            return true;
        }

        assert(true);
        return false;
    }

    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) 
    {
        //栈记录遍历路径,所有祖先结点
        //到达指定结点的路径只有一条
        //深度优先遍历
        stack<TreeNode*> p_st;
        stack<TreeNode*> q_st;
        PreOrder(root, p, p_st);
        PreOrder(root, q, q_st);

        //路径上的相交结点
        while(p_st.size() != q_st.size())
        {
            if(p_st.size() > q_st.size())
                p_st.pop();
            else
                q_st.pop();
        }

        while(p_st.top() != q_st.top())
        {
            p_st.pop();
            q_st.pop();
        }

        return p_st.top();

    }
};

  • 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
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131

2.5 二叉树搜索与双向链表

  1. 题目信息：
    在这里插入图片描述
  2. 题目链接：
    二叉搜索树与双向链表
  3. 思路：记录前置结点，中序遍历，注意调整指针链接的时机
class Solution 
{
public:
	void InOrder(TreeNode* cur, TreeNode*& pre)
	{
		if(cur == nullptr)
		{
			return;
		}

		InOrder(cur->left, pre);
		cur->left = pre;
		if(pre)
			pre->right = cur;
		
		pre = cur;
		InOrder(cur->right, pre);
	}

    TreeNode* Convert(TreeNode* pRootOfTree) 
	{
		if(pRootOfTree == nullptr)
		{
			return nullptr;
		}

		TreeNode* pre = nullptr;
		InOrder(pRootOfTree, pre);
		while(pRootOfTree->left)
		{
			pRootOfTree = pRootOfTree->left;
		}

		return pRootOfTree;
    }
};


  • 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

2.6 从前序与中序遍历序列构造二叉树

  1. 题目信息：
    在这里插入图片描述
  2. 题目链接：
    从前序与中序遍历序列构造二叉树
  3. 思路：根据根分割出左右子树，区域分割，引用
class Solution 
{
public:
    TreeNode* buildNode(vector<int>& preorder, vector<int>& inorder, int& i, int left, int right)
    {
        if(left > right)
        {
            return nullptr;
        }

        //在中序中找到需构建结点
        int j = 0;
        while(inorder[j] != preorder[i])
        {
            j++;
        }

        //根左右
        //构建
        TreeNode* newnode = new TreeNode(preorder[i++]);
        //分割域，判断，构建左孩子
        newnode->left = buildNode(preorder, inorder, i, left, j - 1);
        //分割域，判断，构建右孩子
        newnode->right = buildNode(preorder, inorder, i, j + 1, right);
        
        return newnode;
    }

    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) 
    {
        int i = 0;
        return buildNode(preorder, inorder, i, 0, inorder.size() - 1);
    }
};

  • 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

2.7 从中序与后序遍历序列构造二叉树

  1. 题目信息：
    在这里插入图片描述
  2. 题目链接：
    从中序与后序遍历序列构造二叉树
  3. 思路：区域分割判断，引用，逆向遍历，根右左
class Solution 
{
public:
    TreeNode* buildNode(vector<int>& inorder, vector<int>& postorder, int& i, int left, int right)
    {
        if(left > right)
        {
            return nullptr;
        }

        int j = 0;
        while(inorder[j] != postorder[i])
        {
            j++;
        }

        TreeNode* newnode = new TreeNode(postorder[i--]);
        newnode->right = buildNode(inorder, postorder, i, j + 1, right);
        newnode->left = buildNode(inorder, postorder, i, left, j - 1);

        return newnode;
    }

    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) 
    {
        //逆向遍历，根右左
        int i = postorder.size() - 1;
        return buildNode(inorder, postorder, i, 0, postorder.size() - 1);
    }
};

  • 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

2.8 二叉树前序遍历（非递归）

  1. 题目信息：
    在这里插入图片描述
  2. 题目链接：
    二叉树前序遍历
  3. 思路：根左右，插入右子树时就将根删除，栈记录
class Solution 
{
public:
    vector<int> preorderTraversal(TreeNode* root) 
    {
        //非递归，前序遍历，根左右
        vector<int> ret;
        TreeNode* cur = root;
        stack<TreeNode*> st;
        while(cur || !st.empty())
        {
            while(cur)
            {
                st.push(cur);
                ret.push_back(cur->val);
                cur = cur->left;
            }

            TreeNode* top = st.top();
            st.pop();
            cur = top->right;
        }

        return ret;
    }
};

  • 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

2.9 二叉树中序遍历（非递归）

  1. 题目信息：
    在这里插入图片描述
  2. 题目链接：
    二叉树中序遍历
  3. 思路：插入时机，删除时插入，左右根
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) 
    {
        //中序，左右根
        vector<int> ret;
        stack<TreeNode*> st;
        TreeNode* cur = root;
        //插入时机，删除时插入
        while(cur || !st.empty())
        {
            while(cur)
            {
                st.push(cur);
                cur = cur->left;
            }

            TreeNode* top = st.top();
            st.pop();
            ret.push_back(top->val);

            cur = top->right;
        }

        return ret;
    }
};

  • 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

!!!3.10 二叉树后序遍历（非递归）

  1. 题目信息：
    在这里插入图片描述
  2. 题目链接：
    二叉树后续遍历
  3. 思路：二次遍历时删除，删除时插入，何时删除
class Solution 
{
public:
    vector<int> postorderTraversal(TreeNode* root) 
    {
        //左右根
        vector<int> ret;
        stack<TreeNode*> st;
        TreeNode* cur = root;
        TreeNode* pre = nullptr;
        while(cur || !st.empty())
        {
            //左
            while(cur)
            {
                st.push(cur);
                cur = cur->left;
            }
            
            //根
            TreeNode* top = st.top();
            //cur = st.top();
            if(top->right == nullptr || pre == top->right)
            //if(cur->right == nullptr || pre == cur->right)
            {
                st.pop();
                pre = top;
                //pre = cur;
                ret.push_back(top->val);
                //ret.push_back(cur->val);
            }
            else
            {
                //右，死循环
                cur = top->right;
                //cur调整错误
                //cur = cur->right;
            }
        }

        return ret;
    }
};

  • 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
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/凡人多烦事01/article/detail/464631
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号