专栏首页C++的沉思二叉树常见算法总结和C++实现
原创

二叉树常见算法总结和C++实现

二叉树

知识点

前序遍历:先访问根节点,再前序遍历左子树,然后前序遍历右子树

中序遍历:先中序遍历左子树,再访问根节点,然后中序遍历右子树

后序遍历:先后续遍历左子树,再后续遍历右子树,然后访问根节点

注意:

  • 以根节点访问顺序决定什么遍历
  • 左子树都是优于右子树前序遍历
struct TreeNode
{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

void preorderTraversal(TreeNode* root)
{
    if (root == NULL)
        return;
    cout << root->val << " ";
    preorderTraversal(root->left);
    preorderTraversal(root->right);
}

前序非递归

vector<int> preorderTraversal(TreeNode* root)
{
    vector<int> result;
    if (root == NULL)
        return result;
    stack<TreeNode*> s;
    while (root != NULL || !s.empty()) 
    {
        while (root != NULL)
        {
            result.push_back(root->val);
            s.push(root);
            root = root->left;
        }

        TreeNode* node = s.top();
        s.pop();
        root = node->right;
    }
    return result;
}

中序非递归

vector<int> inorderTraversal(TreeNode* root)
{
    vector<int> result;
    if (root == NULL) 
        return result;
    stack<TreeNode*> s;
    while (root != NULL || !s.empty())
    {
        while (root != NULL)
        {
            s.push(root);
            root = root->left;
        }
        TreeNode* node = s.top();
        s.pop();
        result.push_back(node->val);
        root = node->right;
    }
    return result;
}

后续非递归

核心:根节点必须在右节点弹出之后,再弹出

vector<int> postorderTraversal(TreeNode* root)
{
    vector<int> result;
    if (root == NULL)
        return result;
    stack<TreeNode*> s;
    TreeNode* lastVisit;
    while (root != NULL || !s.empty())
    {
        while (root != NULL)
        {
            s.push(root);
            root = root->left;
        }
        // 这里先看看,不弹出
        TreeNode* node = s.top();
        // 根节点必须在右节点弹出之后,再弹出
        if (node->right == NULL || node->right == lastVisit)
        {
            s.pop();
            result.push_back(node->val);
            lastVisit = node;
        } 
        else
            root = node->right;
    }
    return result;
}

DFS深度搜索-从上到下

// 深度优先
void dfs(TreeNode* root, vector<int>& result)
{
    if (root == NULL)
        return;
    result.push_back(root->val);
    dfs(root->left, result);
    dfs(root->right, result);
}

vector<int> preorderTraversal(TreeNode* root)
{
    vector<int> result;
    dfs(root, result);
    return result;
}

DFS深度搜索-从下到上(分治法)

vector<int> divideAndConquer(TreeNode* root)
{
    vector<int> result;
    if (root == NULL)
        return result;

    // 分治
    vector<int> left = divideAndConquer(root->left);
    vector<int> right = divideAndConquer(root->right);
    // 合并结果
    result.push_back(root->val);
    result.insert(result.end(), left.begin(), left.end()); 
    result.insert(result.end(), right.begin(), right.end()); 
    return result;
}

vector<int> preorderTraversal(TreeNode* root)
{
    return divideAndConquer(root);
}

注意点:

DFS深度搜索(从上到下)和分治法区别:前者一般将最终结果通过引用参数传入,或者一般递归返回结果最终合并

BFS层次遍历

vector<int> levelTraversal(TreeNode* root)
{
    vector<int> result;
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty())
    {
        TreeNode *node = q.front();
        q.pop();
        result.push_back(node->val);
        if (node->left != NULL)
            q.push(node->left);
        if (node->right != NULL)
            q.push(node->right);
    }
    return result;
}

分治法应用

先分别处理局部,再合并结果

适用场景

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (root == NULL)
            return 0;
        int left = maxDepth(root->left);
        int right = maxDepth(root->right);
        return (left > right ? left : right) + 1; 
    }
};

110. 平衡二叉树

给定一个二叉树,判断它是否是高度平衡的二叉树

思路:分治法,左边平衡&&右边平衡&&左右高度差<= 1,因为需要返回是否平衡及高度,要么返回两个数据,要么合并两个数据,所以用-1表示不平衡,>=0表示数高度(二义性:一个变量有两个含义)

class Solution {
public:
    bool isBalanced(TreeNode* root) {
        return (maxDepth(root) == -1) ? false : true;
    }
    int maxDepth(TreeNode* root) {
        if (root == NULL)
            return 0;
        int left = maxDepth(root->left);
        int right = maxDepth(root->right);
        // 为什么返回-1呢?(变量具有二义性)
        if (left == -1 || right == -1 || abs(left - right) > 1)
            return -1;
        return (left > right ? left : right) + 1;
    }
};

注意

一般工程中,结果通过两个变量来返回,不建议用一个变量表示两种含义

124. 二叉树中的最大路径和

给定一个非空二叉树,返回其最大路径和

思路:分治法,分三种情况:左子树最大路径和,右子树最大路径和,左右子树最大加根节点

class Solution {
public:
    int result = INT_MIN;

    int maxPathSum(TreeNode* root) {
        helper(root);
        return result;
    }

    int helper(TreeNode* root)
    {
        if (root == NULL)
            return 0;

        int left = max(helper(root->left), 0);
        int right = max(helper(root->right), 0);

        // 求的过程中考虑包含当前根节点的最大路径
        result = max(result, root->val + left + right);
        // 只返回包含当前根节点和左子树或者右子树的路径,返回上一层和result比较
        return root->val + max(left, right);
    }
};

236. 二叉树的最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先

思路:

两个节点 p,q 分为两种情况:

  • p 和 q 在相同子树中
  • p 和 q 在不同子树中 从根节点遍历,递归向左右子树查询节点信息 递归终止条件:如果当前节点为空或等于 p 或 q,则返回当前节点
  • 递归遍历左右子树,如果左右子树查到节点都不为空,则表明 p 和 q 分别在左右子树中,因此,当前节点即为最近公共祖先;
  • 如果左右子树其中一个不为空,则返回非空节点。
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root == NULL || p == root || q == root)
            return root;
        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        TreeNode* right = lowestCommonAncestor(root->right, p, q);
        if (left != NULL && right != NULL)
            return root;
        return left != NULL ? left : right;
    }
};

102. 二叉树的层序遍历

给你一个二叉树,请你返回其按 层序遍历 得到的节点值。 (即逐层地,从左到右访问所有节点)

思路:用一个队列记录一层的元素,然后扫描这一层元素并添加下一层元素到队列

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> result;
        if (root == NULL)
            return result;

        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty())
        {
            vector<int> level;
            // 记录当前层有多少元素(遍历当前层,再添加下一层)
            int size = q.size();
            for (int i = 0; i < size; i++)
            {
                TreeNode* node = q.front();
                q.pop();
                level.push_back(node->val);
                if (node->left) 
                    q.push(node->left);
                if (node->right)
                    q.push(node->right);
            }
            result.push_back(level);
        }
        return result;
    }
};

107. 二叉树的层次遍历 II

给定一个二叉树,返回其节点值自底向上的层次遍历。 (即按从叶子节点所在层到根节点所在的层,逐层从左向右遍历)

思路:在层级遍历的基础上,翻转一下结果即可

class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        vector<vector<int>> result;
        if (root == NULL)
            return result;

        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty())
        {
            vector<int> level;
            // 记录当前层有多少元素(遍历当前层,再添加下一层)
            int size = q.size();
            for (int i = 0; i < size; i++)
            {
                TreeNode* node = q.front();
                q.pop();
                level.push_back(node->val);
                if (node->left) 
                    q.push(node->left);
                if (node->right)
                    q.push(node->right);
            }
            result.push_back(level);
        }
        // 翻转
        reverse(result.begin(), result.end());
        return result;
    }
};

103. 二叉树的锯齿形层次遍历

给定一个二叉树,返回其节点值的锯齿形层次遍历。(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行)

class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> result;
        if (root == NULL)
            return result;
        queue<TreeNode*> q;
        q.push(root);
        bool isReverse = false;
        while (!q.empty())
        {
            vector<int> level;
            int size = q.size();
            for (int i = 0; i < size; i++)
            {
                TreeNode* node = q.front();
                q.pop();
                level.push_back(node->val);
                if (node->left)
                    q.push(node->left);
                if (node->right)
                    q.push(node->right);
            }
            if (isReverse)
                reverse(level.begin(), level.end());

            result.push_back(level);
            isReverse = !isReverse;  // 是否转置交替进行
        }
        return result;
    }
};

98. 验证二叉搜索树

给定一个二叉树,判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征:

  • 节点的左子树只包含小于当前节点的数。
  • 节点的右子树只包含大于当前节点的数。
  • 所有左子树和右子树自身必须也是二叉搜索树。
class Solution {
public:
    // 中序遍历思想
    bool isValidBST(TreeNode* root) {
        if (root == NULL)
            return true;

        if (!isValidBST(root->left)) 
            return false;
            
        if (prev != NULL && root->val <= prev->val)
            return false;

        prev = root;

        return isValidBST(root->right);
    }
    TreeNode* prev{NULL};
};

701. 二叉搜索树中的插入操作

给定二叉搜索树(BST)的根节点和要插入树中的值,将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 保证原始二叉搜索树中不存在新值。

注意,可能存在多种有效的插入方式,只要树在插入后仍保持为二叉搜索树即可。 你可以返回任意有效的结果。

思路:找到最后一个叶子节点满足插入条件即可

class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        if (root == NULL)
            return new TreeNode(val);
        if (val < root->val)
            root->left = insertIntoBST(root->left, val);
        else
            root->right = insertIntoBST(root->right, val);
        return root;
    }
};

总结

  • 掌握二叉树递归与非递归遍历
  • 理解DFS前序遍历与分治法
  • 理解BFS层次遍历

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 归并快排算法比较及求第K大元素

    核心思想:将数组从中间分成前后两部分,然后对前后两部分分别进行排序,再将排序好的两个部分有序合并在一起,这样整个数组有序。全文图示来源于王争的《数据结构和算法之...

    evenleo
  • C++快速排序原理深究优化

    前面写过一篇关于归并和快排的文章《归并快排算法比较及求第K大元素》,但文中实现的快排算法,在某些极端情况下时间复杂度会退化到 O(n2),效率将是无法接受的。本...

    evenleo
  • KMP算法分析

    KMP 算法是一种改进的字符串匹配算法,KMP 算法是由 D.E.Knuth,J.H.Morris 和 V.R.Pratt 三人提出的,因此人们称它为克努特—莫...

    evenleo
  • leetcode-树 tree

    使用递归,由叶子结点到根结点,每个结点都返回自己所能贡献的最大直径。设一个全局变量用来在过程中更新diameter。

    孔西皮
  • Day18:二叉树的镜像

      由于本题的本质就是考察二叉树,因此还是得用到递归的方法。其实本题就是将二叉树的左右子树进行交换即可。因此我们可以从根节点开始遍历,如果遍历的节点有子结点,就...

    stefan666
  • Binary Tree Level Order Traversal II

    问题:输出二叉树的每一行的结点,从叶子到根 /** * Definition for binary tree * struct TreeNode { * ...

    用户1624346
  • LeetCode 230. Kth Smallest Element in a BST

    ShenduCC
  • 【剑指Offer】54. 二叉查找树的第 K 个结点

    题目描述 给定一棵二叉搜索树,请找出其中的第k小的结点。例如, (5,3,7,2,4,6,8) 中,按结点数值大小顺序第三小结点的值为4。

    瑞新
  • 安装CDSW数据磁盘初始化异常问题分析

    本文主要讲述基于Kerberos环境下的CDH5.13.1版本安装CDSW1.3.0数据磁盘初始化异常问题分析及解决办法。

    Fayson
  • linux基础命令介绍三:文件搜索及其它

    find是一个非常有效的工具,它可以遍历目标目录甚至整个文件系统来查找某些文件或目录:

    用户5030870

扫码关注云+社区

领取腾讯云代金券