[数据结构与算法]数据结构与算法基础之二叉树的遍历方式（一）

二叉树的遍历方式

本笔记均为学习卡哥的代码随想录而记录。
不做商业用途，仅仅是为了学习记录过程。

先来看看二叉树的定义和性质：

二叉树的种类：

满二叉树定义： 如果?棵?叉树只有度为0的结点和度为2的结点，并且度为0的结点在同?层上，则这棵?叉树为满?叉树。
如果深度为K，那节点个数就是2^K-1
完全二叉树： 在完全?叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下??层的节点都集中在该层最左边的若?位置。若最底层为第 h 层，则该层包含 1~ 2^h -1个节点。

插入：堆就是一个完全二叉树，同时保证父子节点的顺序关系。

二叉搜索树： ?叉搜索树是?个有序树。（二叉排序树）
对此，引申出来平衡二叉搜索树：
平衡二叉搜索树：
性质：它是?棵空树或
它的左右两个?树的?度差的绝对值不超过1，并且左右两个?树是?棵平衡?叉树。
具体应用：C++中map、 set、 multimap， multiset的底层实现都是平衡?叉搜索树。
unordered_map、 unordered_set， unordered_map、unordered_map底层实现是哈希表。

二叉树的遍历方式：

1. 深度优先：先往深?，遇到叶?节点再往回?。
   前序遍历（递归法，迭代法）
   中序遍历（递归法，迭代法）
   后序遍历（递归法，迭代法）
2. 广度优先：?层?层的去遍历。
   层次遍历（迭代法）

记住遍历顺序：
前序遍历：中左右
中序遍历：左中右
后序遍历：左右中

递归算法的步骤

1. 确定递归函数的参数和返回值：
确定哪些参数是递归的过程中需要处理的，那么就在递归函数?加上这个参数， 并且还要明确每次递归的返回值是什么进?确定递归函数的返回类型。
2. 确定终?条件：
写完了递归算法, 运?的时候，经常会遇到栈溢出的错误，就是没写终?条件或者终?条件写的不
对，操作系统也是??个栈的结构来保存每?层递归的信息，如果递归没有终?，操作系统的内存
栈必然就会溢出。
3. 确定单层递归的逻辑：
确定每?层递归需要处理的信息。在这?也就会重复调???来实现递归的过程。

关于递归和迭代二叉树深度遍历的方式我已经都写了，再此，谢谢有关注意事项：
递归：很简单，注意仔细；品递归的调用方法。
迭代：通过迭代就需要用栈来实现，通过一个指针遍历和一个容器处理节点元素即可，其中前序遍历和后序遍历的代码逻辑对应；中序遍历的代码逻辑稍微不一样。
因为前序遍历中访问节点（遍历节点）和处理节点（将元素放进result数组中）可以同步处理，但是中序就无法做到同步！
后序迭代:只需要调整顺序：中左右——>中右左——>左右中
贴出代码：

struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
//递归
//前序遍历：
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;
}
};
//中序遍历：
void traversal(TreeNode* cur, vector<int>& vec) {
if (cur == NULL) return;
traversal(cur->left, vec); // 左
vec.push_back(cur->val); // 中
traversal(cur->right, vec); // 右
}
//后序遍历：
void traversal(TreeNode* cur, vector<int>& vec) {
if (cur == NULL) return;
traversal(cur->left, vec); // 左
traversal(cur->right, vec); // 右
vec.push_back(cur->val); // 中
}

//迭代
//前序
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
	stack<TreeNode*> st;
	vector<int> result;
	if (root == NULL) return result;
	st.push(root);
	while (!st.empty()) {
		TreeNode* node = st.top(); // 中
		st.pop();
		result.push_back(node->val);
		if (node->right) st.push(node->right); // 右（空节点不?栈）
		if (node->left) st.push(node->left); // 左（空节点不?栈）
	}
	return result;
}
};
//中序
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
	vector<int> result;
	stack<TreeNode*> st;
	TreeNode* cur = root;
	while (cur != NULL || !st.empty()) {
	if (cur != NULL) { // 指针来访问节点，访问到最底层
		st.push(cur); // 将访问的节点放进栈
		cur = cur->left; // 左
	} else {
		cur = st.top(); // 从栈?弹出的数据，就是要处理的数据（放进result数组?的数据）
		st.pop();
		result.push_back(cur->val); // 中
		cur = cur->right; // 右
	}
	}
	return result;
}
};
//后序
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
	stack<TreeNode*> st;
	vector<int> result;
	if (root == NULL) return result;
	st.push(root);
	while (!st.empty()) {
		TreeNode* node = st.top();
		st.pop();
		result.push_back(node->val);
		if (node->left) st.push(node->left); // 相对于前序遍历，这更改?下?栈顺序 （空节点不?栈）
		if (node->right) st.push(node->right); // 空节点不?栈
	}
	reverse(result.begin(), result.end()); // 将结果反转之后就是左右中的顺序了
	return result;
}
};

二叉树中，递归方法能实现的，迭代也能实现（用栈来实现）。
其中，递归逻辑一样，迭代除了中序，前后序实现逻辑也一样。

统一迭代写法的实现方式
迭代实现的不同之处在于：?法同时解决访问节点（遍历节点）和处理节点（将元素放进结果集）不?致的情况。
解决方法：将访问的节点放?栈中，把要处理的节点也放?栈中但是要做标记。就是要处理的节点放?栈之后，紧接着放??个空指针作为标记。

注意：在代码实现中途曾经忘记过if判断该节点是否为空，要注意条件的判断。并且，弹完节点之后将该结点记得删除。
套模板，绝！！！靠模板也能轻易做出来迭代方法。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        vector<int> result;

        if(root != NULL)
        {
            st.push(root);
        }       
        while(!st.empty())
        {
            TreeNode* node = st.top();
			//错误的及那个st.pop()放入到此处过
            if(node != NULL)
            {   // 将该节点弹出，避免重复操作，下?再将右中左节点添加到栈中         
                st.pop();//必须放在if判断中，因为只有判断node不为空的时候才能删除栈中的结点。
                
                if(node->right != NULL)
                    st.push(node->right);
                st.push(node);// 添加中节点
                st.push(NULL); // 中间点访问过，但是还没有处理，加?空节点做为标记。
                if(node->left != NULL)// 添加左节点（空节点不?栈）
                    st.push(node->left);
            }else
            {// 只有遇到空节点的时候，才将下?个节点放进结果集
                st.pop();// 将空节点弹出
                node = st.top();// 重新取出栈中元素
                st.pop();
                result.push_back(node->val);// 加?到结果集
            }
        }
        return result;
    }
};

刚开始不容易理解，但只要前面的都做出来，后面套用模板就会很快理解并且做出来了。具体每套代码如下：

//后序
while(!st.empty())
        {
            TreeNode *node  = st.top();
            if(node != NULL)
            {
                st.pop();
                st.push(node);
                st.push(nullptr);
                if(node->right)st.push(node->right);
                if(node->left)st.push(node->left);

            }else
            {
                st.pop();
                node = st.top();
                st.pop();
                result.push_back(node->val);
            }
        }
//前序
 while(!st.empty())
        {
            TreeNode *node  = st.top();
            if(node != NULL)
            {
                st.pop();
                if(node->right)st.push(node->right);
                if(node->left)st.push(node->left);
                st.push(node);
                st.push(nullptr);
            }else
            {
                st.pop();
                node = st.top();
                st.pop();
                result.push_back(node->val);
            }
        }
        //中序
        while(!st.empty())
        {
            TreeNode* node = st.top();

            if(node != NULL)
            {               
                st.pop();
                if(node->right != NULL)
                    st.push(node->right);
                st.push(node);
                st.push(NULL);
                if(node->left != NULL)
                    st.push(node->left);
            }else
            {
                st.pop();
                node = st.top();
                st.pop();
                result.push_back(node->val);
            }
        }