二叉树基础-网络避难所

学一个东西，总是要有点兴趣的，不然怎么也学不进去，所以呢，我们了解二叉树之前，我们要知道，为什么我们要了解它呢？也就是它有什么作用呢？

一、为什么使用二叉树？

因为二叉树结合了有序数组，链表这两者的优点。在树中查找数据的速度和有序数组中查找一样快。并且插入数据和删除数据的速度和链表一样。

二、在有序数组中插入数据项太慢

有序数组：数组中的所有数据项都有序的排列。用二分查找可以在有序数组中快速查找特定的值。

过程是先查看数组的中间的数据，如果中间数据比想要的大，缩写范围，在前半段找。反复过程查找的复杂度就是O(logN)。

在有序数组中插入一个新数据，必须要找到新数据插入的位置，然后把所有比新数据大的向后移动一位。这样每次移动都很费时，平均要移动数组中一半的数据（N/2次移动），同理删除也是要多次移动。时间复杂度为O(N)

三、在链表中查找太慢

链表的插入和删除操作都很快，只需要改变一些指针的指向就可以。这些操作的时间复杂度只有O(1).但是在链表中查找数据可不容易。查找必须从头开始，依次访问链表中的每个元素。直到找到所要的数据。因此平均访问N/2个数据项。

不难想到可以通过有序的链表来加快查找速度，链表中的数据项有序的，但这样做没有用的。即使是有序的链表还是必须从头开始依次访问数据项，因为链表中不能直接访问某个数据项，必须通过数据项间的链式引用才行当然有序链表访问结点还是比无序链表快多了，但是查找任意的数据项它无能为力。

四、用树解决问题

二叉树：树中每个结点最多只能有两个子节点。这样的树为二叉树。

二叉搜索树：一个节点的左子节点的关键字值小于父节点，右子值大于等于父节点。

五、入门题：

144.二叉树的前序遍历
145.二叉树的后序遍历
94.二叉树的中序遍历

递归法：

每次写递归，都按照三要素来写！

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

2.确定终止条件：写完了递归算法, 运行的时候，经常会遇到栈溢出的错误，就是没写终止条件或者终止条件写的不对，操作系统也是用一个栈的结构来保存每一层递归的信息，如果递归没有终止，操作系统的内存栈必然就会溢出。

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

以前序遍历为例：

确定递归函数的参数和返回值：因为要打印出前序遍历节点的数值，所以参数里需要传入vector来放节点的数值，除了这一点就不需要再处理什么数据了也不需要有返回值，所以递归函数返回类型就是void，代码如下：

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

确定终止条件：在递归的过程中，如何算是递归结束了呢，当然是当前遍历的节点是空了，那么本层递归就要结束了，所以如果当前遍历的这个节点是空，就直接return，代码如下：

if (cur == NULL) return;

确定单层递归的逻辑：前序遍历是中左右的循序，所以在单层递归的逻辑，是要先取中节点的数值，代码如下：

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

整体代码如下：

/**
 * 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:
    void traversal(TreeNode* cur,vector<int>& value){
        if(cur==NULL) return;
        value.push_back(cur->val);
        traversal(cur->left,value);
        traversal(cur->right,value);
    }
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        traversal(root,res);
        return res;
    }
};

迭代法（非递归）：

以中序遍历为例。

将访问的节点放入栈中，把要处理的节点也放入栈中但是要做标记。

如何标记呢，就是要处理的节点放入栈之后，紧接着放入一个空指针作为标记。

代码如下：

/**
 * 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> preorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*> st;
        if (root != NULL)
            st.push(root);
        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(NULL);
            } else {
                st.pop();
                node = st.top();
                st.pop();
                result.push_back(node->val);
            }
        }
        return result;
    }
};