代码随想录刷题题Day11

刷题的第十一天，希望自己能够不断坚持下去，迎来蜕变。😀😀😀
刷题语言：C++ / Python
Day11 任务
● 理论基础
● 递归遍历
● 迭代遍历
● 统一迭代

1 二叉树理论基础

1.1 二叉树的种类

（1）满二叉树
在这里插入图片描述
深度为 $k$ ，有 $2^k-1$ 个节点的二叉树
（2）完全二叉树

定义：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 $h$ 层（ $h$ 从 $1$ 开始），则该层包含 1~ $2^{h-1}$ 个节点

在这里插入图片描述
优先级队列其实是一个堆，堆就是一棵完全二叉树，同时保证父子节点的顺序关系
（3）二叉搜索树
前面的树，没有数值，而二叉搜索树是有数值的，二叉搜索树是一个有序树

1.若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
2.若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
3.它的左、右子树也分别为二叉排序树

在这里插入图片描述
（4）平衡二叉搜索树
平衡二叉搜索树：又被称为AVL（Adelson-Velsky and Landis）树，是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树

C++中map、set、multimap，multiset的底层实现都是平衡二叉搜索树，所以map、set的增删操作时间时间复杂度是 $l o g n$

1.2 二叉树的存储方式

链式存储和顺序存储

顺序存储的元素在内存是连续分布的，而链式存储则是通过指针把分布在各个地址的节点串联一起

在这里插入图片描述

如果父节点的数组下标是 $i$ ，左孩子就是 $i * 2 + 1$ ，右孩子就是 $i * 2 + 2$

1.3 二叉树的遍历方式

二叉树主要有两种遍历方式：

深度优先遍历：先往深走，遇到叶子节点再往回走。
广度优先遍历：一层一层的去遍历。

深度优先遍历：

前序遍历（递归法，迭代法）中左右
中序遍历（递归法，迭代法）左中右
后序遍历（递归法，迭代法）左右中

这里前中后，其实指的就是中间节点的遍历顺序
在这里插入图片描述
前中后序遍历的逻辑其实都是可以借助栈使用递归的方式来实现的
广度优先遍历

层次遍历（迭代法）

广度优先遍历的实现一般使用队列来实现，这也是队列先进先出的特点所决定的，因为需要先进先出的结构，才能一层一层的来遍历二叉树

这两种遍历是图论中最基本的两种遍历方式

1.4 二叉树的定义

C++：

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

Python：

class TreeNode:
	def __init__(self, val, left = None, right = None):
		self.val = val
		self.left = left
		self.right = right

2 递归遍历

递归的三要素：

确定递归函数的参数和返回值

确定哪些参数是递归的过程中需要处理的，那么就在递归函数里加上这个参数，并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型

确定终止条件

运行遇到栈溢出的错误，就是没写终止条件或者终止条件写的不对，操作系统也是用一个栈的结构来保存每一层递归的信息，如果递归没有终止，操作系统的内存栈必然就会溢出

确定单层递归的逻辑

确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程

前序遍历：
（1）确定递归函数的参数和返回值

void traversal(TreeNode* cur, vector<int>& vec)

（2）确定终止条件

if (cur == NULL) return;

（3）确定单层递归的逻辑
前序遍历是中左右

vec.push_back(cur->val);   // 中
traversal(cur->left, vec); // 左
traversal(cur->right, vec);// 右

C++：

class Solution {
public:
    void traversal(TreeNode* cur, vector<int>& vec)
    {
        if (cur == NULL) return;
        vec.push_back(cur->val);   // 中
        traversal(cur->left, vec); // 左
        traversal(cur->right, vec);// 右
    }
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result;
        traversal(root, result);
        return result;
    }
};

Python：

class Solution(object):
    def preorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        if not root:
            return []
        left = self.preorderTraversal(root.left)
        right = self.preorderTraversal(root.right)
        
        return [root.val] + left + right

中序遍历：
C++：

class Solution {
public:
    void traversal(TreeNode* cur, vector<int>& vec)
    {
        if (cur == NULL) return;
        traversal(cur->left, vec); // 左
        vec.push_back(cur->val);   // 中
        traversal(cur->right, vec);// 右
    }
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        traversal(root, result);
        return result;
    }
};

Python：

class Solution(object):
    def inorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        if not root:
            return []
        left = self.inorderTraversal(root.left)
        right = self.inorderTraversal(root.right)

        return left + [root.val] + right

后序遍历：
C++：

class Solution {
public:
    void traversal(TreeNode* cur, vector<int>& vec)
    {
        if (cur == NULL) return;
        traversal(cur->left, vec);  // 左
        traversal(cur->right, vec); // 右
        vec.push_back(cur->val);    // 中
    }
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> result;
        traversal(root, result);
        return result;
    }
};

Python：

class Solution(object):
    def postorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        if not root:
            return []
        left = self.postorderTraversal(root.left)
        right = self.postorderTraversal(root.right)
        return left + right + [root.val]

3 迭代遍历

递归的实现就是：每一次递归调用都会把函数的局部变量、参数值和返回地址等压入调用栈中，然后递归返回的时候，从栈顶弹出上一次递归的各项参数，所以这就是递归为什么可以返回上一层位置的原因
用栈也可以实现二叉树的前后中序遍历

3.1 前序遍历（迭代法）

前序遍历是中左右，每次先处理的是中间节点，那么先将根节点放入栈中，然后将右孩子加入栈，再加入左孩子。

出栈的时候才是中左右的顺序

在这里插入图片描述
C++：

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
		stack<TreeNode*> st;
		vector<int> result;
		st.push(root);
		while (!st.empty())
		{
			TreeNode* node = st.top();// 中
			st.pop();
			if (node != NULL) result.push_back(node->val);
			else continue;
			st.push(node->right);// 右
			st.push(node->left);// 左
		}
		return result;
    }
};

目前的前序遍历的逻辑无法直接应用到中序遍历上

3.2 后序遍历（迭代法）

在这里插入图片描述
C++：

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        vector<int> result;
        st.push(root);
        while (!st.empty())
        {
            TreeNode* node = st.top();
            st.pop();
            if (node != NULL) result.push_back(node->val);
            else continue;
            st.push(node->left);
            st.push(node->right);
        }
        reverse(result.begin(), result.end()); // 将结果反转之后就是左右中的顺序
        return result;
    }
};

3.3 中序遍历（迭代法）

中序遍历是左中右，先访问的是二叉树顶部的节点，然后一层一层向下访问，直到到达树左面的最底部，再开始处理节点（也就是在把节点的数值放进result数组中），这就造成了处理顺序和访问顺序是不一致的。
在使用迭代法写中序遍历，就需要借用指针的遍历来帮助访问节点，栈则用来处理节点上的元素
在这里插入图片描述

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        TreeNode* cur = root;
        stack<TreeNode*> st;
        while (cur != NULL || !st.empty())
        {
            if (cur != NULL)// 指针来访问节点，访问到最底层
            {
                st.push(cur);// 将访问的节点放进栈
                cur = cur->left;// 左
            }
            else
            {
                cur = st.top();// 从栈里弹出的数据，就是要处理的数据
                st.pop();
                result.push_back(cur->val);// 中
                cur = cur->right;// 右
            }
        }
        return result;
    }
};