当前位置：首页 > article >正文

代码随想录（七） —— 二叉树部分

article 2025/3/13 8:08:00

1. 二叉树的四种遍历方式的理解

前序遍历，中序遍历，后序遍历；层次遍历

结合另一篇博客，关于灵神的题单刷题

二叉树刷题记录-CSDN博客

理解：

在二叉树类型题目中，遍历顺序的选择需要根据具体问题来确定。以下是四种常见的遍历方式及其特点：

一、前序遍历（根左右）

1. 特点：
- 可以在遍历过程中较早地访问根节点，对于需要先处理根节点信息的问题比较适用。
- 常用于需要快速确定整棵树的某些特征，比如构建二叉树的副本、判断两棵二叉树是否相等、求二叉树的深度等问题。

2. 应用场景示例：
- 构建二叉树的副本：先复制根节点，再递归复制左右子树。
- 判断两棵二叉树是否相等：比较根节点的值，然后递归判断左右子树是否相等。

二、中序遍历（左根右）

1. 特点：
- 对于二叉搜索树 BST，中序遍历可以得到有序的节点值序列。
- 在一些需要按特定顺序处理节点的问题中很有用，比如求二叉搜索树的中序后继节点。

2. 应用场景示例：
- 验证二叉搜索树：通过中序遍历得到的序列应该是升序的。
- 求二叉搜索树的第 k 小值：利用中序遍历的有序性，依次计数找到第 k 个节点。

三、后序遍历（左右根）

1. 特点：
- 可以在处理完左右子树后再处理根节点，对于需要在处理完子树后进行一些清理工作或计算依赖于子树结果的问题比较合适。
- 常用于计算二叉树的高度、直径等问题。

2. 应用场景示例：
- 计算二叉树的高度：先计算左右子树的高度，再加上根节点自身的高度。
- 释放二叉树的内存：先递归释放左右子树的内存，再释放根节点的内存。

四、层序遍历

特点
- 从上到下、从左到右依次访问每一层的节点。
适用场景
- 当需要按层次顺序访问二叉树的节点时，层序遍历是合适的选择。
- 在一些图形相关的问题中，如广度优先搜索等，层序遍历可以提供一种按层次处理节点的方式。

此外，还有层序遍历等方式，可根据问题需求灵活选择遍历顺序。在解决二叉树问题时，要充分理解不同遍历方式的特点和适用场景，以便选择最合适的遍历顺序来高效地解决问题。

2. 翻转二叉树

226. 翻转二叉树

遍历顺序分析：

思路是翻转一个节点的左右孩子，处理逻辑应该放在左右孩子之前或之后，所以可以使用前序或者后序遍历，不能使用中序遍历，否则一个节点会翻转两次；比如左孩子翻转之后变成了右孩子，然后右孩子又翻转了一次变成了左孩子。在本题中层序遍历也可以使用。

递归三部曲：（1）确定递归函数的参数与返回值（2）确定终止条件（3）确定单层递归的逻辑

class Solution {
    public TreeNode invertTree(TreeNode root) {
        preOrder(root);
        return root;
    }
    public void preOrder(TreeNode root) {
        if(root == null) return; 
        TreeNode tmp = root.right;
        root.right = root.left;
        root.left = tmp;
        preOrder(root.left);
        preOrder(root.right);
    }
}

//  使用栈来模拟前序遍历：因为前序遍历是根左右顺序，所以入栈方式应当为先入根节点，再加入右节点，最后左节点；
//  这样遍历出来的方式才是根左右
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();  // 遍历中
            // 遍历出中了就进行中节点的操作
            TreeNode* tmp = node->right;
            node->right = node->left;
            node->left = tmp;

            if(node->right) st.push(node->right);
            if(node->left) st.push(node->left);
        } 
        return root;
    }
};

3. 二叉树的最大深度

104. 二叉树的最大深度

二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数或者节点数（取决于深度从0开始还是从1开始）
二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数或者节点数（取决于高度从0开始还是从1开始）

遍历顺序分析：

求二叉树的最大深度就是在求根节点的高度，根节点的高度等于左右子树高度的最大值+1；很显然，这里在处理节点时需要有左右节点的高度，所以最好的选择是使用后序遍历。

class Solution {
public:
    int maxDepth(TreeNode* root) {
        /*
            后序遍历
        */
        return postOrder(root);
    }
private:
    // 返回当前节点的高度
    int postOrder(TreeNode* root) {
        if(root == NULL) {
            return 0;
        } 
        int left = postOrder(root->left);
        int right = postOrder(root->right);
        // 处理当前节点高度
        return max(left,right) + 1;
    }
};

也可以使用层序遍历解决；即二叉树的最大深度即层序遍历的层数

代码

559. N 叉树的最大深度

待办

4. 二叉树的最小深度

111. 二叉树的最小深度

给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明：叶子节点是指没有子节点的节点。

注意：这里有一个坑点，即最小高度并不是左右子树的最小高度 + 1; 因为可能左子树都没有孩子，自然就没有叶子节点了，此时如果按照这种方式计算的话那二叉树的高度会为1，但实际上不是。

所以这里需要把这种情况去掉：

当左子树为空，右子树不为空时，此时该节点最小深度 = 右子树的最小深度 + 1；

当右子树为空，左子树不为空时，此时该节点最小深度 = 左子树的最小深度 + 1；

当左右子树都不是空的时候，此时该节点最小深度 = 左右子树中的最小深度 + 1；

递归终止情况，当该节点为叶子节点时，返回1；或者是该节点为null时返回0，表示没有节点的树最小深度为0。

遍历方式分析

因为在处理节点时需要用到左右子树的信息，所以可以采用后序遍历。

class Solution {
public:
    int minDepth(TreeNode* root) {
        return postOrder(root);
    }
private:
    int postOrder(TreeNode* root) {
        if(root == NULL) return 0;
        int leftMin = postOrder(root->left);
        int rightMin = postOrder(root->right);
        // 处理逻辑
        if(root->left == NULL && root->right != NULL) {
            return rightMin + 1;
        }
        if(root->left != NULL && root->right == NULL) {
            return leftMin + 1;
        }
        return min(leftMin, rightMin)  + 1; // 叶子节点 以及 左右子树都存在的节点 其返回值都是这个
    }
};

5. 完全二叉树的节点数

222. 完全二叉树的节点个数

给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。

完全二叉树的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。

遍历顺序分析：

对于普通的一颗二叉树，

递归的思想：二叉树的节点数目 = 左子树的节点数 + 右子树的节点数 + 1；

层序遍历的思想：就是一层一层的遍历，直到队列变空

class Solution {
public:
    int countNodes(TreeNode* root) {
        /*
            后序遍历
        */
        return postOrder(root);
    }

private: 
    // 返回子树的高度
    int postOrder(TreeNode* root) {
        if(root == NULL) {
            return 0;
        }
        int left = postOrder(root->left);
        int right = postOrder(root->right);
        return left + right + 1;
    }
};

class Solution {
public:
        /*
            层序遍历
        */
    int countNodes(TreeNode* root) {
        if(root == NULL) return 0;
        queue<TreeNode*> que;
        que.push(root);  // --> 准备op: 建队并根节点入队
        int res = 0;
        while(!que.empty()) { 
            int size = que.size();  // 控制每一层的遍历次数
            for(int i=0; i< size; i++) {
                TreeNode* node = que.front();
                que.pop(); // 元素出队
                res ++; // 记录节点数目
                if(node -> left) que.push(node->left);
                if(node -> right) que.push(node -> right); // 左右孩子节点入队
            }
        }
        return res;
    }
};