代码随想录Day14 | 二叉树、递归遍历、迭代遍历、统一迭代

二叉树

文档讲解：代码随想录
视频讲解： 关于二叉树，你该了解这些！| 二叉树理论基础一网打尽，二叉树的种类、二叉树的存储方式、二叉树节点定义、二叉树的遍历顺序
>状态

二叉树基础

种类

1. 满二叉树：度为0或2 层数为k 节点数为$2^k-1$
2. 完全二叉树：除最后一层，其余层都是满的二叉树，最后一层从左到右依次填充 – 大顶堆和小顶堆
3. 二叉搜索树：父节点的左子节点值小于父节点值，右子节点值大于父节点的值
4. 平衡二叉树(AVL)：在搜索树的前提下，任意左子树与对应的右子树高度差不大于1 – map set multimap multiset 查询和插入时间复制度O(logn)

存储方式

1. 链式存储：链表，一个节点有两个指针来维护左子树和右子树
2. 线性存储：数组，对于下标i的元素其左右子结点下标分别为$2i+1,2i+2$

遍历方式

1. BFS：层序遍历 、迭代法，利用队列实现
2. DFS：递归实现，前序中序后序，递归或者迭代实现，利用栈
3. 前序后序中序：就是中间节点的位置

前序遍历：中左右
中序遍历：左中右
后序遍历：左右中

定义

//回顾链表的定义
struct ListNode*
{
	int val;
	ListNode* next;
	ListNode(int x):val(x),next(nullptr){}
};

//二叉树链式存储
struct TreeNode
{
	int val;
	TreeNode* left;
	TreeNode* right;
	TreeNode(int x):val(x),left(nullptr),right(nullptr){}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

二叉树的递归遍历

文档讲解：代码随想录
视频讲解： 每次写递归都要靠直觉？ 这次带你学透二叉树的递归遍历
状态

递归要点

1. 确定递归函数的参数和返回值：参数为递归函数中内部处理的数据，返回值决定了递归函数的返回类型
2. 终止条件：递归的实现就是栈的工作，没有达到终止条件之间一直压入当前代码，当到达终止条件后从栈顶Pop
3. 单层递归的逻辑：重复的处理逻辑

递归前序遍历

1. 递归的参数和返回值：要处理的就是每个节点，然后我们用一个数组来存储返回的节点，所以不需要返回值，如果有那么应该是一个vector
2. 终止条件，就是当这个节点为空的时候，终止函数
3. 递归逻辑：将当前节点输入到数组中，并调用其左子节点或者右子节点使用该函数

void returnTree(TreeNode* cur,vector<int>& list)
{	
	//先判断，防止访问指针出错
	if(cur== nullptr) return ;
	//按顺序递归 中左右
	list.push_back(cur->val);
	returnTree(cur->left,list);
	returnTree(cur->right,list);
}
1
2
3
4
5
6
7
8
9

递归中序遍历

void returnTree(TreeNode* cur,vector<int>& list)
{	
	//先判断，防止访问指针出错
	if(cur== nullptr) return ;
	//按顺序递归 左右
	returnTree(cur->left,list);
	lust.push_back(cur->val);
	returnTree(cur->right,list);
}
1
2
3
4
5
6
7
8
9

递归后序遍历

void returnTree(TreeNode* cur,vector<int>& list)
{	
	//先判断，防止访问指针出错
	if(cur== nullptr) return ;
	//按顺序递归 左右
	returnTree(cur->left,list);
	returnTree(cur->right,list);
	lust.push_back(cur->val);
}
1
2
3
4
5
6
7
8
9

二叉树的迭代遍历

文档讲解：代码随想录
视频讲解：
状态

利用栈来实现遍历。整个迭代分为两个步骤

处理：将元素放进数组中
访问：遍历节点

前序

首先压入头节点，然后取出头节点的时候压入右节点和左节点（先入后出满足中左右），之后每当取出一个节点都要将其的右子节点和左子节点压入，直到取出节点的左子节点为空。
需要先判断当前树是否为空，如果为空直接返回

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> treestack;
        if(root!=nullptr) treestack.push(root);
        while(!treestack.empty())
        {
            //暂存，方便取左子和右子
            TreeNode* temp = treestack.top();
            //存放
            res.push_back(temp->val);
            //弹出
            treestack.pop();
            //将右子节点压入
            if(temp->right) treestack.push(temp->right);
            //左子节点压入
            if(temp->left) treestack.push(temp->left);
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

中序

左中右，我们就不能像前序那样了，因为前序的处理和访问都是中节点，所以只需要一个中节点指针控制，而中序我们访问的是中节点，但实际处理的是左子节点。所以可以增加一个指针来控制返回结果的存储。

class Solution {

public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> treestack;
        TreeNode* temp = root;
        while(temp!=nullptr || !treestack.empty())
        {
            //头节点开始所有左节点的压入
            if(temp!=nullptr)
            {
                treestack.push(temp);
                temp = temp->left;
                
            }
            //此时temp为最左节点
            else
            {
                temp = treestack.top();
                treestack.pop();
                res.push_back(temp->val);
                //将处理指针指向最左端节点的右子树
                temp = temp->right;
                //如果不为空，则将访问第二个最左边的节点
                //如果为空，则将访问最左节点的中节点，其也为最左边节点
            }
            
        }
        return res;
    }
};
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

后序

虽然我们处理的和访问的仍然不是一个指针，甚至变得更多，但发现如果将前序迭代的结果变成中右左，然后将结果翻转是不是就是左右中了呢。所以我们只需要修改前序迭代的遍历就可以了。

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> treestack;
        if(root!=nullptr) treestack.push(root);

        while(!treestack.empty())
        {
            TreeNode* temp = treestack.top();
            res.push_back(temp->val);
            treestack.pop();
            if(temp->left) treestack.push(temp->left);
            if(temp->right) treestack.push(temp->right);
        }

        int left = 0;
        int right = res.size()-1;
        while(left<right)
        {
            swap(res[left++],res[right--]);
        }
        return res;
    } 
};
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

迭代法遍历的统一写法–不太理解

具体参考
同样考虑处理和访问的节点，我们对要访问的节点在访问入栈之后加上标记，如果出现这个标记则开始进行处理。
栈在开始处理之前的最后一步访问，此时栈里面右整个树的所有节点。
而我们访问的永远都是中节点，并且记住栈是先进后出，所以对于中序遍历左中右，入栈方式应该是右中左，然后在中节点后加上null，右中null左。
对于前序，入站方式就是右左中Null，后序就是中null右左。
当我们遇到null就开始处理元素存入数组的操作