数据结构：二叉树

已于 2024-09-22 19:18:00 修改
阅读量1.2k 收藏 16
点赞数 14
分类专栏： 数据结构 代码随想录 文章标签： 数据结构 算法
于 2024-09-22 18:48:55 首次发布
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/Input_print/article/details/142441230
版权

数据结构：二叉树

二叉树基础

常见的特殊二叉树

满二叉树、完全二叉树、二叉搜索树、平衡二叉树、平衡二叉搜索数、红黑树；

满二叉树：二叉树中每个节点要么没有孩子，要么既有左孩子又有右孩子；

完全二叉树：二叉树中除了最后一层，其余层节点都达到最大值，并且最后一层节点都尽可能靠左排列；

二叉搜索树：二叉搜索树的定义是递归的——任何一个节点都满足其左子树的所有节点的值小于该节点的值，其右子树的所有节点的值均大于该节点的值；（并不能从局部判断一颗二叉树是不是二叉搜索树，比如通过判断左孩子小于自己，右孩子大于自己就说满足二叉搜索树，一定是判断左子树均小于自己，右子树均大于自己才能说满足二叉搜索树）

平衡二叉树：任意节点的左右子树的高度差不超过1；

平衡二叉搜索树：同时具有平衡二叉树和二叉搜索树性质的二叉树，红黑树就是一种自平衡的二叉搜索树，C++中map、set、multimap、multiset的底层就是红黑树；

二叉树的存储方式

链式存储和顺序存储：链式存储是使用链表存储二叉树，顺序存储是使用数组存储二叉树；

二叉树的结构体定义（链式存储）：

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {} // 构造函数
};

// TreeNode* root = new TreeNode(1); // 新建二叉树结点，注意返回的是指针，用指针接受

二叉树的遍历

二叉树的遍历方式有很多：

  • 前序遍历、中序遍历、后序遍历（注意都有两种实现方式：递归和迭代）
  • 层次遍历（使用辅助数据结构队列实现）
  • 深度优先遍历、广度优先遍历（图论中常用的遍历方式，深度优先遍历使用栈，广度优先遍历使用队列）

递归遍历

递归算法实现的三要素：

  1. 确定递归函数的传入参数和返回值类型；
  2. 确定递归退出条件（一定要提前确定，防止死循环）；
  3. 确定单层递归逻辑；

递归算法的代码模板：

递归返回值 traversal (递归参数) {
    if (递归终止条件) return 返回值;
    单层递归逻辑；
}

前序遍历、中序遍历、后序遍历的递归实现上的代码结构基本一致，只是在单层递归逻辑的递归顺序上有所不同。

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); // 右节点
       */
       
       /* 中序遍历
       traversal(cur->left, vec); // 左节点
       vec.push_back(cur->val); // 中间节点
       traversal(cur->right, vec); // 右节点
       */
       
       // 后序遍历
       traversal(cur->left, vec); // 左节点
       traversal(cur->right, vec); // 右节点
       vec.push_back(cur->val); // 中间节点
   }  
}

前中后序遍历只是在遍历节点的顺序上不同；前序遍历是先处理根节点，然后处理左右节点；中序遍历是先处理左节点（即cur->left），然后处理根节点（cur），最后处理右节点（cur->right）；后序遍历的顺序是左右中；

迭代遍历

递归遍历的思路简单，实现代码也少；但是只要是递归就有可能出现递归栈溢出，所以迭代遍历也要掌握。递归使用了递归栈，在栈中保存了自己的函数调用（包括参数、局部变量、返回地址等），即在栈中维护了中间状态；改为迭代时，同样要维护对应的中间状态，所以使用辅助数据结构栈来实现迭代；

无论如何，我们访问节点的顺序都是从根出发，一层层往下访问；可是我们的处理节点的顺序却不一定是一层层往下的；节点的访问顺序和节点的处理顺序不一致导致了迭代遍历比递归遍历更具难度。

例如，后序遍历的节点处理顺序是左右中，即整颗二叉树最左下角的节点反而是最先被处理的元素；可是我们一开始是没办法中间访问左下角元素的，节点访问顺序一定是从根节点出发，然后一直left，即在第一个要处理的节点之前，我们已经访问了很多没有被处理的节点；

下面是一颗二叉树：
        1
      2   3
    4   5
  6
后序遍历序列：[6 4 5 2 3 1]
首先要处理最左下角的节点，即节点6；要处理节点，首先要访问到节点，从节点1出发先到达节点6
从节点1到达节点6一共访问的节点：[1 2 4 6]
访问的节点也要保存起来，用辅助数据结构栈（不可能每次都从根节点出发找处理节点，太耗时）
节点6出栈后处理节点6，处理完之后怎么找下一个被处理节点？节点6是节点4的左孩子，后序遍历处理顺序是左右中，所以节点6处理完之后，找节点4的右孩子（或者右子树中最左边的节点）
辅助栈：
    [1 2 4 6] // 处理节点6，节点6出栈
    [1 2 4] // 处理节点4，节点4出栈
    [1 2 5] // 节点4处理完之后，看节点4的右兄弟，处理节点5，节点5出栈
    [1 2] // 处理节点2，节点2出栈
    [1 3] // 节点2处理完之后，看节点2的右兄弟，处理节点3，节点3出栈
    [1] // 处理节点1，节点1出栈
    [] // 栈空，结束
出栈顺序就是后序遍历序列

上述过程描述了一颗简单的二叉树使用辅助栈实现迭代后序遍历的过程；实现的关键就是将访问节点保存在栈内，处理节点在栈顶，处理完节点后栈顶出栈，然后将处理节点的父节点的右子树按照一定规则入栈；

思路上已经清楚，但是在一些细节上需要搞清楚：

  • 什么时候将栈顶结点拿出来处理？后序遍历是左右中，所以要处理的节点一定是相对其他节点最左下；所以当栈顶结点不能继续往左下走时，就出栈并处理（具体而言，如果栈顶结点是cur，发现cur->left == NULL且cur->right == NULL均为true时，出栈处理）
  • 栈顶节点处理完毕后出栈，然后找哪些节点入栈？应该考虑不同情况；
    • 出栈节点的父节点就是出栈后栈的新栈顶节点；
    • 如果出栈节点是其父节点的右孩子：说明父节点没有左孩子，左右中，父节点已经在栈顶了，所以不用再入栈，直接处理父节点即可；
    • 如果出栈节点是其父节点的左孩子：父节点还可能有右子树，所以继续分情况讨论：
      • 父节点没有右子树，即cur->right == NULL为true，直接处理父节点；
      • 父节点有右子树，找到该右子树中的最左下角节点，从该右子树的根到最左下角节点的直接路径上访问过的所有节点均入栈；

什么叫最左下角节点？

  • 从节点出发一直访问左孩子，直到没有左孩子可以访问；
  • 此时看是否能访问右孩子，如果没有右孩子，则已经找到最左下角节点；
  • 如果有右孩子，则访问右孩子，然后再重复第一步过程；

（最左下角节点未必是某个节点的左孩子，也可能是右孩子，但是最左下角节点一定是一个叶子节点）

      1
   2      3
     4  5   6
最左下角节点为4（从第三层最左边找），4是2的右孩子；

代码实现：（后序遍历迭代法实现）二叉树的后序遍历

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        stack<TreeNode*> st; // 辅助数据结构：栈；
        vector<int> result; // 记录后序遍历序列；
        if (root == NULL) return result;
      	// 根节点入栈；
        st.push(root);
        // 找到左下角节点；
        TreeNode* cur = root;
        while (!st.empty()) {
        	if (cur->left != NULL) { // 优先向左走；
                cur = cur->left;
                st.push(cur);
                continue; 
            } else if (cur->right != NULL) { // 左边没办法走了，才走右边
            	cur = cur->right;
                st.push(cur);
                continue;
            } else { // 到达最左下节点，即到达要处理的节点；
                result.push_back(cur->val);
                st.pop(); // 出栈
                if (st.empty()) break; // 如果不break，下一句的st.top()会溢出；
                if (cur == st.top()->left) st.top()->left = NULL;
                if (cur == st.top()->right) st.top()->right = NULL; // 已经处理过的节点从树中删除，防止再处理；
                cur = st.top();
            }            
        }
        return result;
    }
};

后序遍历是前中后序遍历中最难的部分，所以只要将后序遍历迭代算法的思路搞清楚，余下两个其实简单了很多！

后序遍历的另一种实现：后序遍历是左右中，前序遍历是中左右，所以其实只用将前序遍历代码改为中右左，然后reverse（反转数组），即可得到后序遍历序列；而前序遍历的代码其实简单了不少，因为前序遍历节点访问顺序和处理顺序一致；（注意算法思想：左右中难，中右左可不难，求中右左，最后反转即可）

前序遍历是中左右——调整代码左右循环顺序——变成中右左——反转result数组——左右中——实现后序遍历是左右中；

代码实现：（前序遍历迭代法实现）二叉树的前序遍历

二叉树前序遍历（迭代法） 
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
		stack<TreeNode*> st; // 注意是TreeNode*而不是TreeNode；
        vector<int> result;
        if (root == NULL) return result;
        st.push(root);  // 栈中存的是节点访问顺序；
        TreeNode* cur = root;
        while (!st.empty()) {
            // 栈顶元素出栈，记录result；
            cur = st.top();
            result.push_back(cur->val);
            st.pop();
            // 出栈之后将右孩子先进栈，然后进左孩子（入栈顺序和出栈顺序相反）
            if (cur->right != NULL) st.push(cur->right);
            if (cur->left != NULL) st.push(cur->left);
        }
        return result;
    }
};

代码实现：（中序遍历迭代法实现）二叉树的中序遍历

二叉树中序遍历（迭代法）

中序遍历先找到最左边节点，但是这个左边和后序遍历的左下角不一样，这个左边节点可以不是叶子节点，只要一直left即可，不用right；

class Solution {
    public:
    vector<int> inorderTraversal(TreeNode* root) {
        stack<TreeNode*> st; // 注意是TreeNode*而不是TreeNode；
        vector<int> result;
        if (root == NULL) return result;
        st.push(root);  // 栈中存的是节点访问顺序；
        TreeNode* cur = root;
        while (cur != NULL || !st.empty()) { // 中序遍历
            if (cur != NULL) { // 指针来访问节点，访问到最底层
                st.push(cur); // 将访问的节点放进栈
                cur = cur->left;                // 左（一直left直到无法left，此时为第一个要处理的节点）
            } else {
                cur = st.top(); // 从栈里弹出的数据，就是要处理的数据（放进result数组里的数据）
                st.pop();
                result.push_back(cur->val);     // 中
                cur = cur->right;               // 右
            }
        }
        return result;
    }
};

前序遍历节点访问顺序和节点处理顺序一致，而后序遍历和中序遍历节点访问顺序和节点处理顺序不一致；前序遍历先处理整棵树中的根节点，中序遍历最先处理整棵树的最左边节点，后序遍历最先处理整棵树最左下角节点；最终上述三者实现代码差异很大；

统一所有风格的迭代法：

统一风格的解决方法：做标记，访问节点入栈，处理节点也入栈，但是处理节点入栈后做标记，那我们就将访问的节点放入栈中，把要处理的节点也放入栈中但是要做标记。如何标记呢，就是要处理的节点放入栈之后，紧接着放入一个空指针作为标记。 这种方法也可以叫做标记法。

中序遍历迭代（统一写法）

做完标记之后，处理节点和访问节点就可以区分开了；处理节点之间输出到result数组，访问节点需要根据遍历的方式做进一步处理；

核心问题：

  • 处理节点的处理方式：直接出栈，然后写result数组；
  • 访问节点的处理方式：出栈，然后看左孩子、右孩子，按照一定顺序将左孩子、右孩子、该节点、NULL入栈（注意入栈顺序和我们要的遍历序列顺序要相反）；
  • 访问节点如何才能变成处理节点：访问节点被出栈后，再次入栈即可变成处理节点；

访问节点不一定是当前处理节点，所以先将访问节点弹出栈（很关键），弹出栈之后，就可以看访问节点的结构，比如左孩子、右孩子有没有，然后根据选择的遍历顺序，重新将左孩子、右孩子、访问节点按照特定顺序入栈；（如此入栈完之后，访问节点就可以变成处理节点，所以访问节点入栈后可以做标记）

代码实现：

class Solution {
public:
    vector<int> inorderTraversal(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);  // 添加右节点（空节点不入栈）
                st.push(node);                          // 添加中节点（刚刚已经弹出来，避免了此时重复操作，弹出就可以重新调整顺序！）
                st.push(NULL); // 中节点访问过，但是还没有处理，加入空节点做为标记。
                if (node->left) st.push(node->left);    // 添加左节点（空节点不入栈）
                */
                /* 前序遍历（出栈顺序中左右，入栈顺序右左中，刚好相反）
                if (node->right) st.push(node->right);  // 右
                if (node->left) st.push(node->left);    // 左
                st.push(node);                          // 中
                st.push(NULL);
                */
                
                /* 后序遍历（出栈顺序左右中，入栈顺序中右左，刚好相反）
                st.push(node);                          // 中
                st.push(NULL);
                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); // 加入到结果集
            }
        }
        return result;
    }
};

层次遍历

二叉树的层次遍历：利用辅助数据结构队列；

102二叉树的层序遍历

核心思想：所有队列中元素全部依次出队，同时出队节点的左右孩子依次入队；（出队同时也要考虑入队！）

为什么要队列中所有元素都要出队？要搞清楚队列中所有元素代表什么，代表的是一层；也就是每一次while循环都会让1层元素出队，然后让下一层元素全部入队；

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        queue<TreeNode*> que;
        if (root != NULL) que.push(root);
        vector<vector<int>> result; // 二维向量，可以体现出节点的层次关系（不只是层次遍历序列）
        while (!que.empty()) {
            int size = que.size(); // 1层元素的数量
            vector<int> vec;
            for (int i = 0; i < size; i++) { // for循环1层元素入队，1层元素出队
                TreeNode* node = que.front();
                que.pop();
                vec.push_back(node->val);
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
            }
            result.push_back(vec);
        }
        return result;
    }
};

直接作为层次遍历的模板，一定要牢记过程，然后直接使用；

二叉树题目（部分题目）

题目描述思路
翻转二叉树调换每个节点的左孩子和右孩子递归三部曲、前序遍历（也可以前序遍历的迭代法实现）
对称二叉树检查二叉树是否镜像对称递归，分为内侧对称和外侧对称，两个都对称时才能说整体对称
二叉树的最大深度返回二叉树的最大深度递归，使用后序遍历访问节点；注意而二叉树最大深度的获取方式：左右子树深度中的较大者加一
二叉树的最小深度返回二叉树的最小深度迭代，选择层次遍历，返回层次遍历过程中第一次发现叶子节点时的深度
完全二叉树的节点个数返回二叉树结点个数递归：左子树节点数加右子树节点数加1即树的节点个数；迭代法在处理节点时维护一个节点计数器
平衡二叉树判断二叉树是否是平衡二叉树递归：判断左子树高度减去右子树高度的绝对值小于等于1；
翻转二叉树

将二叉树的左孩子和右孩子反转（每个节点的左右孩子都反转，可以直接使用递归实现）

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (root == NULL) return root;
        swap(root->left, root->right);
        invertTree(root->left);
        invertTree(root->right);
        return root;
    }
};

直接使用递归三部曲递归的模板，对每个节点都反转左右孩子；既然提到了每个节点，就要访问二叉树的每个节点，即遍历二叉树，选择前序或者后序遍历的递归实现都可以（甚至层次遍历）；如果使用中序遍历，某些节点的左右孩子可能反转2次，所以不好；

这道题目背后有一个让程序员心酸的故事，听说 Homebrew的作者Max Howell，就是因为没在白板上写出翻转二叉树，最后被Google拒绝了。

迭代法：

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (root == NULL) return root;
        stack<TreeNode*> st;
        st.push(root);
        while(!st.empty()) {
            TreeNode* node = st.top();              // 中
            st.pop();
            // result.push_back(cur->val);
            swap(node->left, node->right); // 之前这里时保存val到result，现在改为swap左右孩子；
            if(node->right) st.push(node->right);   // 右
            if(node->left) st.push(node->left);     // 左
        }
        return root;
    }
};

前序遍历的迭代法我们已经实现了，把前序遍历的迭代法当成模板；然后在处理每一个节点时，不是将节点的val保存起来，而是交换左右孩子；

可以从代码看出，我们只是改变了一句话，即可从求二叉树前序遍历序列变成翻转二叉树！

对称二叉树

镜像对称而不是左右子树相同就叫对称！但是也是比较两棵树（即左子树和右子树），并不是比较两棵树同一位置的节点是否相同，而是判断”对应“节点是否相同；

对应节点，比如树1和树2，树1的左孩子对应树2的右孩子，树1往左走树2就往右走；

将树分为内侧和外侧，分别判断，只有内侧外侧均相同才是对称；

class Solution {
public:
    bool compare(TreeNode* left, TreeNode* right) {//传入的是左子树和右子树
        if (left == NULL && right != NULL) return false;
        else if (left != NULL && right == NULL) return false;
        else if (left == NULL && right == NULL) return true;
        else if (left->val != right->val) return false;

        //此时才判断左右是否对称；（用递归，分外侧和内侧）
        bool outside = compare(left->left, right->right);
        bool inside = compare(left->right, right->left);
        bool isSame = outside && inside;
        return isSame;
    }
    bool isSymmetric(TreeNode* root) {
        if (root == NULL) return true;
        return compare(root->left, root->right);
    }
};

重点时每一步的判断逻辑（划分内外侧、提前结束等操作）

也可以使用层次遍历迭代法实现，同一层中节点的值是否关于中间对称；

二叉树的最大深度

依旧是递归实现，选择后序遍历来访问每一个节点；

注意二叉树最大深度的定义：左子树和右子树的深度中的最大值加一作为二叉树的最大深度；

class Solution {
public:
    int getdepth(TreeNode* node) {
        if (node == NULL) return 0; //递归终止条件；
        int leftdepth = getdepth(node->left);
        int rightdepth = getdepth(node->right);
        int depth = max(leftdepth, rightdepth) + 1;
        return depth;
    }
    int maxDepth(TreeNode* root) {
        return getdepth(root);
    }
};

// 精简之后代码：看不出递归三部曲、看不出遍历方式：
class solution {
public:
    int maxDepth(TreeNode* root) {
        if (root == null) return 0;
        return 1 + max(maxDepth(root->left), maxDepth(root->right));
    }
};
二叉树的最小深度

使用层次遍历，在层次遍历过程中第一次发现叶子节点就返回；

代码实现就是层次遍历的标准模板，然后加上一个深度计数器和判断叶子节点的逻辑；

class Solution {
public:
    int minDepth(TreeNode* root) {
        // 使用层次遍历（队列）；
        if (root == NULL) return 0; //提前判断结束；
        queue<TreeNode*> que; //新建队列；
        int depth = 0;
        // 层次遍历主体过程（一层进队列，一层出队列）
        que.push(root); //根节点进入队列；
        while (!que.empty()) { //队列不为空则一直循环；
            int size = que.size(); //size是一层节点数；
            depth++; //每向下一层，深度加一；
            for (int i = 0; i < size; i++) {
                TreeNode* node = que.front(); //取出队头节点；
                que.pop();
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
                if (!node->left && !node->right) { //第一次到叶子节点；
                    return depth;
                }
            }
        }
        return 0;
    }
};
完全二叉树的节点个数

递归：获取左子树节点个数、获取右子树节点个数，左子树节点数加右子树节点数再加1即二叉树的节点数。（递归，每个子树和原来树的操作方式一致，所以使用递归）

class Solution {
private:
    // 使用后序遍历，递归法；
    int getNodesNum(TreeNode* cur) {
        if (cur == NULL) return 0; //提前停止；
        // 递归逻辑：任何一颗子树的节点数=子树的左子树节点数+子树右子树节点数+1；
        int leftNum = getNodesNum(cur->left); //左
        int rightNum = getNodesNum(cur->right); //右
        int result = leftNum + rightNum + 1;
        // 返回逻辑；
        return result;
    }
public:
    int countNodes(TreeNode* root) {
        return getNodesNum(root);
    }
};

层次遍历也可以，迭代法的思路更简单，在处理节点时维护一个节点计数器即可；

平衡二叉树

判断平衡的依据：左子树高度减去右子树高度的绝对值小于等于1；

 /*
    要求比较高度，高度从下到上看，所以使用后序遍历；
    如果比较深度，深度从上到下看，所以使用前序遍历；
 */
class Solution {
private:
    int getHeight(TreeNode* node) { //获取树的高度（递归、后序遍历）
        if (node == NULL) return 0;
        int result = 0; //相当于信号，-1代表不平衡；其余代表树高度；
        // 明确单层递归的逻辑；
        // 左子树和右子树高度之差=绝对值（左子树高度-右子树高度）
        int leftHight = getHeight(node->left); //左
        if (leftHight == -1) return -1;
        int rightHight = getHeight(node->right); //右
        if (rightHight == -1) return -1;
        int lrDiff = abs(leftHight - rightHight);
        if (lrDiff > 1) { //中；高度差大于1，说明不平衡；
            result = -1; 
        } else {
            result = 1 + max(leftHight, rightHight);
        }
        return result;
    }
public:
    bool isBalanced(TreeNode* root) {
        return getHeight(root) == -1 ? false : true;
    }
};

求深度和高度的不同：求深度可以从上到下去查 所以需要前序遍历（中左右），而高度只能从下到上去查，所以只能后序遍历（左右中）；

深度描述的是从根节点到当前节点的路径长度，通过前序遍历（根-左-右）可以逐层向下遍历，同时记录每个节点的深度信息，因此比较适合用来求深度。

高度描述的是从当前节点到最远叶子节点的路径长度，通过后序遍历（左-右-根）可以从叶子节点向上逐层计算高度，因此比较适合用来求高度。

二叉树的所有路径

使用回溯法：路径往前走，走到尽头要往后走，往回走就是回溯；回溯不仅要回退指针，还要回退上下文（回退前入栈回退后就要出栈，要一一对应）；

257.二叉树的所有路径

class Solution {
    private:
    // 递归函数
    void traversal(TreeNode* cur, vector<int>& path, vector<string>& result) {
        path.push_back(cur->val); //中间节点；(即使是叶子节点也要加入到path中，所以写在前面)
        //确定递归终止条件：找到叶子节点；
        if (cur->left == NULL && cur->right == NULL) {
            //终止处理逻辑：path中存放的是路径中节点的编号，我们要将path中消息转换为字符串存在result中；
            //做的是字符串拼接，让输出格式满足题意；
            string sPath;
            for (int i = 0; i < path.size() - 1; i++) {
                sPath += to_string(path[i]);
                // sPath += '->'; //加入的不应该是一个字符，而是字符串
                sPath += "->";
            }
            sPath += to_string(path[path.size() - 1]);
            result.push_back(sPath);
            return;
        }
        //递归的单层逻辑：记录路径中节点信息到path中；
        //确定使用的遍历方式：前序遍历；先处理中间节点；
        //path.push_back(cur->val); //中间节点；
        if (cur->left) { //左
            traversal(cur->left, path, result); 
            path.pop_back(); //回溯；（回溯和递归是一起的，永远不会分开）
        }
        if (cur->right) { //右
            traversal(cur->right, path, result);
            path.pop_back(); //回溯；（回溯和递归是一起的，永远不会分开）
        }
    }
    public:
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> result;
        vector<int> path;
        if (root == NULL) return result; //traversal()里没有判断传入为NULL的逻辑，所以外面要加；
        traversal(root, path, result);
        return result;
    }
};
从中序与后序遍历序列构造二叉树

手算：后序数组的最后一个元素为切割点，先切中序数组，根据中序数组，反过来再切后序数组。一层一层切下去，每次后序数组最后一个元素就是节点元素。

106.从中序与后序遍历序列构造二叉树

代码实现：切割时一定要保持区间一致性！

class Solution {
    private:
    TreeNode* traveral(vector<int>& inorder, vector<int>& postorder) {
        //切割两个数组；
        //如果数组大小为0，则说明是空节点；
        if (postorder.size() == 0) return NULL;
        //切割数组，根据后序遍历数组最后一个元素切割中序遍历数组；
        int rootValue = postorder[postorder.size() - 1];
        TreeNode* root = new TreeNode(rootValue); //后序遍历最后一个元素是根；

        //如果数组只有一个元素，即只有一个根节点；二叉树就是这个根节点；
        if (postorder.size() == 1) return root;
        // 不管是判断大小为0还是1，都是为了提前判断尽量避免切割；

        //找切割点（在中序遍历数组中找rootValue）
        int delimiterIndex; //切割点
        for (delimiterIndex = 0; delimiterIndex < inorder.size(); delimiterIndex++) { //遍历整个中序数组，找到分割点
            if (inorder[delimiterIndex] == rootValue) break;
        }
        //分割点所在的秩为delimiterIndex;
        //切割中序数组，得到中序左数组和中序右数组；（注意数组切割的stl）切割点的元素不要了；
        //左闭右开区间：[0, delimiterIndex)
        vector<int> leftInorder(inorder.begin(), inorder.begin() + delimiterIndex);
        //[delimiterIndex + 1, end)
        vector<int> rightInorder(inorder.begin() + delimiterIndex + 1, inorder.end());

        //舍弃后序数组最后一个元素；
        postorder.resize(postorder.size() - 1);

        //根据中序左数组和中序右数组的长度来切割后序数组；（左数组在数组前部分，左数组大小和中序左数组相同）[0, leftInorder.size)注意是左开右闭；
        vector<int> leftPostorder(postorder.begin(), postorder.begin() + leftInorder.size());
        //[leftInorder.size(), end]
        vector<int> rightPostorder(postorder.begin() + leftInorder.size(), postorder.end());

        // root->left = traveral(中序左数组，后序左数组);
        // root->right = traveral(中序右数组，后序右数组); //中序右数组长度等于后序右数组；
        root->left = traveral(leftInorder, leftPostorder);
        root->right = traveral(rightInorder, rightPostorder); 

        return root;
    }
    public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        if (inorder.size() == 0 || postorder.size() == 0) return NULL;
        return traveral(inorder, postorder);
    }
};

总结

二叉树的题目一般都要访问二叉树的所有节点；访问节点，就是遍历，选择什么遍历（前中后序遍历、层次遍历），要递归还是迭代，甚至选择图论的深度优先遍历或者广度优先遍历；

至于其他的要求，求什么节点数、左叶子之和等 其实就是选择合适的遍历方式之后加上特定的判断逻辑；

前中后序遍历的迭代写法要知道，递归人人都会，迭代才是差距；

递归函数要不要返回值？有时候我们要接受左子树和右子树递归之后的返回值，比如左子树是否平衡，右子树是否平衡，要调用递归函数之后返回高度等；如果有返回值，一般是后序遍历，先递归函数传入左孩子，然后递归函数传入右孩子，然后根据两次递归的返回值进行处理（递归单层逻辑在最后）

有时候，二叉树的题目还要用到回溯，比如求路径，递归和回溯一定是绑定的，递归前操作了什么，回溯时要一一对应恢复回去；

二叉树、平衡二叉树、完全二叉树、满二叉树
Terry的IT世界
11-07 9万+
基本概念结点的层次（Level）从根开始定义，根为第一层，根的孩子为第二层。二叉树的高度：树中结点的最大层次称为树的深度（Depth）或高度。 二叉树在计算机科学中，二叉树是每个结点最多有两个子树的有序树。通常子树的根被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用作二叉查找树和二叉堆。二叉树的每个结点至多只有二棵子树(不存在
数据结构：二叉树相关代码
08-24
在IT领域，数据结构是计算机科学的基础，而二叉树作为一种重要的数据结构，广泛应用于算法设计、数据库系统、编译器等。这个压缩包“数据结构：二叉树相关代码”很可能包含了各种二叉树操作的实现，如插入、删除、...
满二叉树和完全二叉树
foreverhuylee的专栏
08-07 9283
二叉树分类很多，其中满二叉树哦和完全二叉树比较特殊，因为这两种二叉说效率很高，这里记录几条相关性质。   首先是满二叉树：从形象上来说满二叉树是一个绝对的三角形，也就是说它的最后一层全部是叶子节点，其余各层全部是非叶子节点，如果用数学公式表示那么其节点数n=2^k-1其中k表示深度，也就是层数。也就是说满二叉树的节点数是一系列固定的数，比如说，1,3,7,15...如果节点数不是这个序列中的数
各种二叉树的介绍
雪村一郎的博客
04-10 2万+
数据结构中有很多种类的树结构，例如，普通二叉树、完全二叉树、满二叉树、线索二叉树、哈夫曼树、二叉搜索树（排序树）、平衡二叉树、AVL平衡二叉树、红黑树、B树、B+树、堆 1、普通二叉树、完全二叉树、满二叉树 二叉树：最多有两棵子树的树被称为二叉树 满二叉树：二叉树中所有非叶子结点的度都是2，且叶子结点都在同一层次上 完全二叉树：如果一个二叉树与满二叉树前m个节点的结构相同，这样的二叉树被称
二叉树的分类
weixin_34232363的博客
03-06 240
满二叉树 　　通过名字就可以看出来是一个满的二叉树，意思也就是二叉树上每一层的结点数都达到了最大。看上去就像上个三角形。 　　满二叉树必须满足： 　　　　1.总的结点个数2k-1个结点; 如上图是一个3层的二叉树，总的结点个数为23-1=7个点节 　　　...
二叉树、完全二叉树、完满二叉树、满二叉树
流华追梦的专栏
06-08 2318
简单定义：每个节点最多只有2个子节点的树叫做二叉树。专业定义：二叉树是n(n>=0)个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树组成。下图为一棵普通二叉树。
非线性数据结构：二叉树的遍历算法详解
12-03
内容概要：本文详细介绍了二叉树的基本概念、...其他说明：二叉树作为基础的非线性数据结构，在许多高级数据结构和算法中起着重要作用。文章提供的理论知识和代码示例，有助于读者系统地掌握二叉树的相关知识和技能。
数据结构：二叉树层次遍历算法解析及C语言实现
最新发布
12-03
以二叉链表作为二叉树的存储结构，编写以下算法： （5）计算二叉树最大的宽度（二叉树的最大宽度是指二叉树所有层中结点个数的最大值）。 分析 • 求最大宽度可采用层次遍历的方法，记下各层结点数， • 每层遍历...
数据结构：二叉树的应用
04-25
一、 实验目的： ...3. 按照二叉树的结构输出二叉树； 4. 三种不同遍历算法遍历此二叉树； 5. 查找某人在二叉树中的位置，要求输出从根结点至查找结点的路径； 6. 统计二叉树的深度，输出叶子结点的信息。
数据结构：二叉树链表并遍历输出
07-13
数据结构：二叉树链表并遍历输出
二叉树的几种类型
weixin_30294021的博客
08-24 415
本文基于邓俊辉编著的《数据结构（C++语言版）（第3版）》和网上博文，仅介绍完全二叉树、满二叉树，平衡二叉树的相关概念。 一、二叉树 1、二叉树的概念 二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree），其次序不能任意颠倒。（百度百科） 2、性质 （1）若二叉树的层次从0开始，则在二叉树的第i层至多...
满二叉树
一只不开窍的笨鸟
09-29 873
满二叉树是在一棵二叉树中，所有的分支节点都存在左子树和右子树，并且所有的叶子节点都是在同一层上。     叶子节点只能出现在最下面一层。 非叶子结点的度一定为2，也就是必须要有左右左右子树。 同样深度的二叉树，满二叉树拥有最多的节点，叶子的个数也是最多的。
二叉树（完美二叉树、完全二叉树、完满二叉树）
热门推荐
老人家独爱茉莉的博客
10-11 2万+
二叉树（完美二叉树、完全二叉树、完满二叉树）树的概念树的基本术语二叉树（Binary Tree)什么是二叉树（Binary Tree)二叉树的性质完美二叉树(Perfect Binary Tree)完全二叉树(Complete Binary Tree)完满二叉树(Full Binary Tree)比较区分完美二叉树 v.s. 完全二叉树完满(Full)二叉树 v.s. 完全(Complete)二叉...
二叉树之满二叉树
weixin_50221415的博客
03-02 428
二叉树之满二叉树
二叉树，满二叉树，真二叉树
weixin_45638349的博客
09-03 840
树形结构 这是我们最熟悉的线性结构，线性结构的数据简单来说就是一条线，串起来一个个的节点。 那树形结构是怎样的呢？很明显，顾名思义，它是一棵树的样子。 将这棵树进行180度大翻转，就成了数据结构中的树形结构了 可以初步看出，二叉树就是每个节点要么没有分枝，要么就是分两根枝，而多叉树的每个节点可以有任意的分枝。 生活中的树形结构 文件夹的管理就是我们生活中最常见的树形结构 如下图就是上图文件夹组织形式的树化形式，可以看出我，文件夹的管理是一棵多叉树，一个文件夹下可以有很多子文件夹。 将文件归类，易于
二叉树 完全二叉树 满二叉树
KK_DU
11-07 764
基本概念 结点的层次（Level）从根开始定义，根为第一层，根的孩子为第二层； 二叉树的高度：树中结点的最大层次称为树的深度（Depth）或高度 ； 二叉树 在计算机科学中，二叉树是每个结点最多有两个子树的有序树。通常子树的根被称作“左子树”（left subtree）和“右子树”（right subtree）； 1.二叉树的基本形态： 二叉树也是递归定义的
树、二叉树、满二叉树、完全二叉树
X女王的博客
04-19 259
树的特点 有且仅有一个根结点 除根结点外，有且只有一个直接前驱 有零个或多个直接后继 结点的度和树的深度 结点的度（Degree）：结点拥有的子树数。如上图中，A的度为3 树的深度（Depth）：树中结点的最大层次称为树的深度。如上图，树的深度为4 二叉树的特点 每个结点至多只有两颗子树 二叉树的子树有左右之分，其次序不能任意颠倒 下图是二叉树的5种基本形态： 二叉树的性质...
Java实现数据结构：二叉树专题代码解析
在众多数据结构中，二叉树是一种基础且广泛使用的结构，它在计算机科学领域具有重要地位。二叉树是一种非线性数据结构，具有以下特点： 1. 每个节点最多有两个子节点，分别为左子节点和右子节点。 2. 左子节点的值...
评论
添加红包

请填写红包祝福语或标题

个

红包个数最小为10个

元

红包金额最低5元

当前余额3.43元 前往充值 >
需支付：10.00元
成就一亿技术人!
领取后你会自动成为博主和红包主的粉丝 规则
hope_wisdom
发出的红包

打赏作者

OutlierLi

你的鼓励将是我创作的最大动力

¥1 ¥2 ¥4 ¥6 ¥10 ¥20
扫码支付：¥1
获取中
扫码支付

您的余额不足，请更换扫码支付或充值

打赏作者

实付元
使用余额支付
点击重新获取
扫码支付
钱包余额 0

抵扣说明：

1.余额是钱包充值的虚拟货币，按照1:1的比例进行支付金额的抵扣。
2.余额无法直接购买下载，可以购买VIP、付费专栏及课程。

余额充值