概述

树是一种常用的数据结构，用于模拟具有树状结构性质的数据集合。

树里面的每一个节点都有一个值和一个包含所有子节点的列表。从图的观点来看，树也可以被视为一个拥有N个节点和N-1条边的有向无环图。

二叉树是一种典型的树状结构，每个节点最多有两个子树，分别被称为左子树和右子树。

学习目标

1. 掌握树和二叉树的概念
2. 熟悉不同的遍历方法
3. 运用递归解决二叉树相关的题目

树的遍历

二叉树的前序遍历

首先访问根节点，然后遍历左子树，最后遍历右子树。(根->左->右

例题：现有一个二叉树的根节点root，返回它的节点值的前序遍历

示例1:

输入：root=[1,null,2,3]

输出：[1,2,3]

递归解法

首先创建一个数组用于记录数组

创建一个preOrder方法用于前序遍历的递归调用，以中->左->右的顺序将值填写到结果集和中，最后返回。

    vector<int> preorderTraversal(TreeNode *root) {
        vector<int> ans;
        preOrder(root,ans);
        return ans;
    }
    void preOrder(TreeNode *root,vector<int> &ans){//该方法用于递归调用，接收两个参数，分别是根节点的地址和结果
//&ans指的是这里的ans表示引用，对ans的操作相当于对传入参数的内存地址进行操作
        if(root == nullptr)return;//如果根节点为空则直接返回
        ans.push_back(root->val);
        preOrder(root->left,ans);//递归调用
        preOrder(root->right,ans);//顺序为中->左->右
    }

注：

关于函数参数中的"*“和”&"符号的意思，以下面这个方法为例

void CreatTree(BitNode* &list);

BitNode*可以看作一个整体表示变量类型是一个LNode类的指针

&list中的&符号表示引用实参，即代表实参数的一个别名。

有的小伙伴可能会问：&不是取地址符吗，为啥变成引用参数了？

因为&在变量定义区，表示引用，在变量操作区表示取地址。

利用栈和队列的解法

首先回顾一下，栈的特点是LIFO，即后入先出。

第一步先让根节点入栈，当根节点入栈成功后，进入一个循环

该循环的过程为

1. 先记下根节点的值，然后用pop弹出栈顶
2. 如果右节点非空，则将右节点压入
3. 如果左节点非空，则将左节点压入

这样取出的顺序就会是根/左/右，符合前序遍历的顺序要求。

    vector<int> preorderTraversal(TreeNode *root) {
        TreeNode* p=root;
        vector<int> ans;
        if(root!= nullptr){
            stack<TreeNode*> st;
            st.push(p);//根节点入栈//LIFO
            while (!st.empty()){//如果栈非空
                p = st.top();//返回栈顶节点
                ans.push_back(p->val);//先记录下根节点的值
                st.pop();//弹出栈顶节点
                if(p->right != nullptr){//让右边先入栈
                    st.push(p->right);
                }
                if(p->left!= nullptr){//左边后入栈，这样出来的时候左边比右边优先
                    st.push(p->left);
                }
            }
        }
        return ans;
    }

二叉树的中序遍历

中序遍历的顺序要求是：左子树->根节点->右子树

例题：现有一个二叉树的根节点root，返回它的中序遍历。

示例1

输入：root=[1,null,2,3]

输出：[1,2,3]

递归解法

递归解法就贼简单了，左边优先添加到数组中然后返回就行了。

    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> ans;
        inorderOrder(root,ans);
        return ans;
    }
    void inorderOrder(TreeNode* root,vector<int> &ans){
        if(root== nullptr)return;
        inorderOrder(root->left,ans);
        ans.push_back(root->val);
        inorderOrder(root->right,ans);
    }

栈解法

首先让根节点入栈，然后进入一个循环。

前期循环（即if里面的语句）是为了从根节点到左子树方向遍历并放到栈中，由于栈是先入后出（FILO）的特性，那么最后取出的时候左子树优先于根节点。

后期循环（即else里面的片段），目的是为了将栈中的元素取出，慢慢向右移动，如果移动到最右边或者栈为空时则退出循环。

    vector<int> inorderTraversal(TreeNode* root) {
        TreeNode* p = root;
        stack<TreeNode*>stack;
        vector<int> res;
        if(root != nullptr){
            while(!stack.empty() || p != nullptr){
                if(p != nullptr){//首先，先把二叉树从根节点一直向左边遍历边入栈
                    //以从中到左的顺序放到栈里面去
                    stack.push(p);     
                    p = p->left;
                }else{//当遍历到最左边时
                    //将栈中的元素从栈顶取出，并向右子树移动
                    p = stack.top(); 
                    stack.pop();
                    res.push_back(p->val);
                    p = p->right;//这一行是为了和while的第二个条件配合
                }//这样最后取出来的就是左->中->右的顺序了。
            }
        }
        return res;
    }

二叉树的层序遍历

简介

层序遍历就是逐层遍历树结构。

广度优先搜索DFS是一种广泛运用在树或图这列数据结构中。遍历或搜索的算法。

该算法从一个根节点开始，首先访问节点本身，然后遍历它的二级相邻节点，三级相邻节点。以此类推。

简单来说就是从上到下，一层一层地遍历

例题：二叉树的层序遍历

给定一个二叉树的根节点root，返回其节点值的层序遍历，即逐层从左到右访问所有节点。

例如

输入 root=[3,9,20,null,null,15,7]

输出 [[3],[9,20],[15,7]]

BFS解法

本题明显适合使用广度优先搜索(BFS)算法。

第一步

1. 创建一个二维数组(ans)用于存放和返回答案
2. 创建一个队列用于层序遍历

首先检查一下这个root是不是空的，要是空的直接返回了

非空的话就接着下一步：让根节点入队。

至此我们就可以开启一个BFS循环了

• 首先是一个while循环，条件是队列非空，要是空了的话就说明结束了
  1. 创建一个临时数组用于记录层数据
  2. 获取这一层的节点数levelNum
     • 然后是套一个for循环，共循环levelNum次
       1. 让队列前面的节点出列，放到一个node里
       2. 出列完记得用pop方法删掉
       3. 将出列节点的值放到临时数组中，用于记录答案
       4. 将该节点的非空左子树和右子树依次放入到队列末尾
  3. 将临时数组加到答案数组(ans)中去
• 最后返回答案数组即可

代码如下

    vector<vector<int>> levelOrder(TreeNode *root) {
        vector<vector<int>> ans;
        if (root == nullptr)return ans;//如果是空就直接返回了。
        queue<TreeNode *> queue;//队列
        queue.push(root);//根节点入队
        while (!queue.empty()) {//循环到队为空
            vector<int> sublist;//创建一个临时数组用于记录层数据
            int levelNum = queue.size();//获得这一层的节点数
            for (int i = 0; i < levelNum; ++i) {
                TreeNode *node = queue.front();//前面的节点，出列！
                queue.pop();//出列完记得删掉
                sublist.push_back(node->val);//将出列的节点添加到答案数组中
                //然后依次将节点到左子树和右子树加入队列
                if (node->left != nullptr)queue.push(node->left);
                if (node->right != nullptr)queue.push(node->right);
            }
            ans.push_back(sublist);//将临时数组存放到层数据添加到答案中去
        }
        return ans;//返回答案
    }

---