代码随想录训练营第十四天 |递归法解决二叉树的遍历

1.二叉树

1.1满二叉树

只有度为0和度为2的结点，度为0的结点在同一层，深度为k，有2^k-1个结点。

2.完全二叉树

除了最底层结点没填满，其余每层结点数都达到最大值，且最底层结点都集中在最左边。

3.二叉搜索树

①左子树不为空，则左子树上所有节点值均小于它的根节点的值。

②左子树不为空，则左子树上所有节点值均大于于它的根节点的值。

二叉搜索左小右大

4.平衡二叉搜索树 AVL

空树或者它的两个左右子树的高度差绝对值不超过1，并且左右两个子树都是平衡二叉树。

C 中map，set，multimap，multiset底层实现都是平衡二叉树，所以map，set增删操作时间复杂度为logn。unordered_map、unordered_map底层实现是哈希表。

5.二叉树的存储方式

二叉树可以用指针链式存储，也可以用数组顺序存储。

数组的话，若父节点数组下标是i，那么左孩子下标是i×2 1，右孩子是i×2 2。

6.二叉树的遍历方式

①深度优先遍历：先往深走，遇到叶子节点再往回走，一般用栈实现。

前序遍历：中左右

中序遍历：左中右

后序遍历：左右中

前中后 指的是中间节点的遍历顺序

②广度优先遍历一层一层遍历，一般用队列实现

层次遍历

7.递归基础

三要素：①确定递归函数的参数和返回值

②确定终止条件

③确定单层循环逻辑

7.1前序遍历代码

class Solution{
public:
    //vec定义了一个栈（数组）
    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);   //root根节点
		return result;
	}
};

中序遍历：

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

这篇好文章是转载于：学新通技术网