概述

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

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

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

学习目标

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

树的遍历

二叉树的前序遍历

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

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

示例1:

img

输入: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

img

输入: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,返回其节点值的层序遍历,即逐层从左到右访问所有节点。

例如

img

输入 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;//返回答案
    }

Q.E.D.