leetcode之二叉树刷题总结(C++)

  • Post author:
  • Post category:其他



基础知识:

所有的题都是建立在二叉树的前序遍历,中序遍历,后序遍历(它们的递归版与非递归版),及层次遍历。搜索二叉树及平衡二叉树。搜索二叉树是指按照中序遍历,它是从小到大排序的(所以考搜索二叉树基本考中序遍历)。平衡二叉树是指根节点的左右子树总结点相差不能超过1。

参考代码:(上面的遍历方式标准版)

#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <queue>

using namespace std;

struct tree_node{
	int val;
	tree_node* left;
	tree_node* right;
	tree_node(int x) :val(x), left(NULL), right(NULL){}
};

class Solution{
public:
	//前序遍历,递归与非递归版,根 左 右
	void front_d(tree_node* head)
	{
		if (head == NULL)
			return;

		cout << head->val << endl;
		front_d(head->left);
		front_d(head->right);
	}
	void front(tree_node* head)
	{
		if (head == NULL)
			return;

		stack<tree_node*> node_stack;
		tree_node* pMove = head;

		while (pMove || !node_stack.empty())
		{
			while (pMove)
			{
				cout << pMove->val << endl;
				node_stack.push(pMove);
				pMove = pMove->left;
			}

			if (!node_stack.empty())
			{
				pMove = node_stack.top();
				node_stack.pop();

				pMove = pMove->right;
			}
		}
	}

	//中序遍历,递归和非递归版,左 根 右
	void middle_d(tree_node* head)
	{
		if (head == NULL)
			return;

		middle_d(head->left);
		cout << head->val << endl;
		middle_d(head->right);
	}

	void middle(tree_node* head)
	{
		if (head == NULL)
			return;

		stack<tree_node*> node_stack;
		tree_node* pMove = head;

		while (pMove || !node_stack.empty())
		{
			while (pMove)
			{
				node_stack.push(pMove);
				pMove = pMove->left;
			}

			if (!node_stack.empty())
			{
				pMove = node_stack.top();
				node_stack.pop();
				cout << pMove->val << endl;

				pMove = pMove->right;
			}
		}
	}

	//后序遍历,递归与非递归版,左 右 根
	void back_d(tree_node* head)
	{
		if (head == NULL)
			return;

		back_d(head->left);
		back_d(head->right);
		cout << head->val << endl;
	}

	void back(tree_node* head)
	{
		if (head == NULL)
			return;

		stack<tree_node*> node_stack;
		tree_node* pMove = head;
		tree_node* flag = NULL;

		while (pMove)
		{
			node_stack.push(pMove);
			pMove = pMove->left;
		}

		while (!node_stack.empty())
		{
			pMove = node_stack.top();
			node_stack.pop();

			if (pMove->right == NULL || pMove->right == flag)
			{
				cout << pMove->val << endl;
				flag = pMove;
			}
			else{
				node_stack.push(pMove);
				pMove = pMove->right;

				while (pMove)
				{
					node_stack.push(pMove);
					pMove = pMove->left;
				}
			}
		}
	}
	//奇偶层次遍历
	void cc_traverse(tree_node* head)
	{
		if (head == NULL)
			return;
		
		queue<tree_node*> odd_q;
		queue<tree_node*> even_q;
		
		tree_node* pMove = head;
		odd_q.push(head);
		while (!odd_q.empty() || !even_q.empty())
		{
			while (!odd_q.empty())
			{
				pMove = odd_q.front();
				odd_q.pop();
				cout << pMove->val << " ";
				if (pMove->left)
					even_q.push(pMove->left);
				if (pMove->right)
					even_q.push(pMove->right);
			}
			cout << endl;

			while (!even_q.empty())
			{
				pMove = even_q.front();
				even_q.pop();
				cout << pMove->val << " ";
				if (pMove->left)
					odd_q.push(pMove->left);
				if (pMove->right)
					odd_q.push(pMove->right);
			}
			cout << endl;
		}
	}
};

int main()
{
	Solution solution;
	tree_node tree_node1(1);
	tree_node tree_node2(2);
	tree_node tree_node3(3);
	tree_node tree_node4(4);
	tree_node tree_node5(5);
	tree_node tree_node6(6);
	tree_node tree_node7(7);

	tree_node1.left = &tree_node2;
	tree_node1.right = &tree_node3;

	tree_node2.left = &tree_node4;
	tree_node2.right = &tree_node5;

	tree_node3.left = &tree_node6;
	tree_node3.right = &tree_node7;

	tree_node4.left = NULL;
	tree_node4.right = NULL;

	tree_node5.left = NULL;
	tree_node5.right = NULL;

	tree_node6.left = NULL;
	tree_node6.right = NULL;

	tree_node7.left = NULL;
	tree_node7.right = NULL;

	solution.cc_traverse(&tree_node1);

	system("pause");
	return 0;
}


上面是必备基础知识,下面是力扣1-150题中的二叉树题目:


博客索引:

94.二叉树的中序遍历:

https://blog.csdn.net/L_smartworld/article/details/107365297

95.不同的二叉搜索树 II:

https://blog.csdn.net/L_smartworld/article/details/107365448

96.不同的二叉搜索树:

https://blog.csdn.net/L_smartworld/article/details/107365789

98.验证二叉搜索树:

https://blog.csdn.net/L_smartworld/article/details/107406797

100.相同的树:

https://blog.csdn.net/L_smartworld/article/details/107406978

101.对称二叉树:

https://blog.csdn.net/L_smartworld/article/details/107407096

102.二叉树的层序遍历:

https://blog.csdn.net/L_smartworld/article/details/107407314

103. 二叉树的锯齿形层次遍历:

https://blog.csdn.net/L_smartworld/article/details/107407697

104. 二叉树的最大深度:

https://blog.csdn.net/L_smartworld/article/details/107411335

105. 从前序与中序遍历序列构造二叉树:

https://blog.csdn.net/L_smartworld/article/details/107411449

106. 从中序与后序遍历序列构造二叉树:

https://blog.csdn.net/L_smartworld/article/details/107411641

107. 二叉树的层次遍历 II:

https://blog.csdn.net/L_smartworld/article/details/107427667

108. 将有序数组转换为二叉搜索树:

https://blog.csdn.net/L_smartworld/article/details/107427704

109. 有序链表转换二叉搜索树:

https://blog.csdn.net/L_smartworld/article/details/107427762

110. 平衡二叉树:

https://blog.csdn.net/L_smartworld/article/details/107427795

111.二叉树的最小深度:

https://blog.csdn.net/L_smartworld/article/details/107463981

112.路径总和:

https://blog.csdn.net/L_smartworld/article/details/107464166

113.路径总和 II:

https://blog.csdn.net/L_smartworld/article/details/107464369

114.二叉树展开为链表:

https://blog.csdn.net/L_smartworld/article/details/107464575

116.填充每个节点的下一个右侧节点指针:

https://blog.csdn.net/L_smartworld/article/details/107492388

117.填充每个节点的下一个右侧节点指针 II:

https://blog.csdn.net/L_smartworld/article/details/107492618

124.二叉树中的最大路径和:

https://blog.csdn.net/L_smartworld/article/details/107541464

129.求根到叶子节点数字之和:

https://blog.csdn.net/L_smartworld/article/details/107700110

144.二叉树的前序遍历:

https://blog.csdn.net/L_smartworld/article/details/107761716

145.二叉树的后序遍历:

https://blog.csdn.net/L_smartworld/article/details/107761779

235.二叉搜索树的最近公共祖先:

https://blog.csdn.net/L_smartworld/article/details/107245923

236.二叉树的最近公共祖先:

https://blog.csdn.net/L_smartworld/article/details/107246390


剑指offer:(最新版,与上面重复就不罗列了)

8.二叉树的下一个节点:

https://blog.csdn.net/L_smartworld/article/details/105490529

26.树的子结构:

https://blog.csdn.net/L_smartworld/article/details/104655031

27.二叉树的镜像:

https://blog.csdn.net/L_smartworld/article/details/104655595

33.二叉搜索树的后序遍历序列:

https://blog.csdn.net/L_smartworld/article/details/104793879

37.序列化二叉树:

https://blog.csdn.net/L_smartworld/article/details/105583848

54.二叉搜索树的第K大节点:

https://blog.csdn.net/L_smartworld/article/details/105611668



版权声明:本文为L_smartworld原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。