前一篇文章介绍了二叉树基本的遍历源代码，这篇文章介绍一些二叉树的算法应用。

代码的编写都是基于c++11规范，Linux下gcc编译执行通过。（gcc version 9.4.0 (Ubuntu 9.4.0-1ubuntu1~20.04.1)）。

首先我们定义一个节点结构体

#include <iostream>template<typename T>struct BinaryTreeNode {    BinaryTreeNode *left;   // 左子树    BinaryTreeNode *right;  // 左子树    BinaryTreeNode *parent; // 父节点，寻找节点的前驱和后继需要用到    T value;     // 值    BinaryTreeNode() : left(nullptr), right(nullptr), parent(nullptr) {}    BinaryTreeNode(T t) : left(nullptr), right(nullptr), parent(nullptr), value(t) {}    // 我们重写操作符，能够打印节点信息；需要注意一些语法信息    template<class U>    friend std::ostream& operator<<(std::ostream& out, const BinaryTreeNode<U> node);};template<typename U>std::ostream& operator<<(std::ostream& out, const BinaryTreeNode<U> node) {    out << node.value;    return out;}

前面写了二叉树遍历的基本算法，掌握好二叉树的递归遍历，leetcode上关于二叉树的easy级别的问题基本都能解决了。下面是实现一些二叉树的经典算法。

为了寻找前驱和后继节点，节点结构体定义增加了parent指针，指向自己的父节点，在前一篇的二叉树反序列化工具需要做一小点修改，增加父节点的赋值。

BinaryTreeNode<std::string>* preOrderUnSerialize(std::queue<std::string>& list,                                                 BinaryTreeNode<std::string>* parent = nullptr) {    if (list.empty()) return nullptr;    std::string s = list.front();    list.pop();    BinaryTreeNode<std::string>* curr = nullptr;    if (s != "null") {        curr = new BinaryTreeNode<std::string>(s);        curr->parent = parent;        curr->left = preOrderUnSerialize(list, curr);        curr->right = preOrderUnSerialize(list, curr);    }    return curr;}// 记得销毁template<typename T>void destroy(BinaryTreeNode<T>* head) {    if (head->left != nullptr) destroy(head->left);    if (head->right != nullptr) destroy(head->right);    delete head;}

为了方便测试，增加一个find函数，用来在生成的树里找到节点，来做后面的测试

/** * @brief 寻找节点，按先序，找到第一个相等节点则返回，找不到返回空 *  * @tparam T  * @param t  * @return BinaryTreeNode<T>*  */template<typename T>BinaryTreeNode<T>* find(BinaryTreeNode<T>* head, const T& t) {    if (head == nullptr) {        return nullptr;    }    if (head->value == t) return head;    BinaryTreeNode<T>* b0 = find(head->left, t);    if (b0 != nullptr) return b0;    BinaryTreeNode<T>* b1 = find(head->right, t);    if (b1 != nullptr) return b1;    return nullptr;}

前驱是指在中序遍历序列中，一个节点的上一个节点。

/** * @brief 寻找前驱 * 中序遍历中，一个节点的前一个节点 * 寻找前驱节点需要用到节点的parent属性 * 1. 节点有左子树，前驱是左子树的最右节点 * 2. 节点无左子树 *   2.1 节点是父节点的右节点，返回父节点 *   2.2 节点是父节点的左节点，找到祖先节点中第一个是某个节点右节点的父节点返回(这需要好好理解) * * @param node * @return 前驱节点 */template<typename T>BinaryTreeNode<T>* predecessor(BinaryTreeNode<T>* node) {    if (node == nullptr) {        return nullptr;    }    BinaryTreeNode<T> *ptr = node;    if (ptr->left != nullptr) {        ptr = ptr->left;        while (ptr->right != nullptr) {            ptr = ptr->right;        }        return ptr;    } else {        if (ptr->parent != nullptr) {            if (ptr == ptr->parent->right) {                return ptr->parent;            }            ptr = ptr->parent;            while (ptr != nullptr) {                if (ptr->parent != nullptr && ptr == ptr->parent->right) {                    return ptr->parent;                }                ptr = ptr->parent;            }        }    }    return nullptr;}

后继是指在中序遍历序列中，一个节点的下一个节点

/** * @brief 寻找后继 * 后继是指中序遍历中，一个节点的后一个节点 * 寻找后继节点需要用到节点的parent属性 * 1. 节点有右子树，后继是右子树的最左节点 * 2. 节点没有右子树 *   2.1 节点是父节点的左节点，后继就是父节点 *   2.2 节点是父节点的右节点，顺着父节点向上，找到第一个节点其是其父节点的左节点，返回这个节点的父节点 *  * @return 后继节点 */template<typename T>BinaryTreeNode<T>* successor(BinaryTreeNode<T>* node) {    if (node == nullptr) {        return nullptr;    }    BinaryTreeNode<T> *ptr = node;    if (ptr->right != nullptr) {        ptr = ptr->right;        while (ptr->left != nullptr)  {            ptr = ptr->left;        }        return ptr;    } else {        if (ptr->parent != nullptr) {            if (ptr == ptr->parent->left) {                return ptr->parent;            }                    ptr = ptr->parent;            while (ptr != nullptr) {                if (ptr->parent != nullptr && ptr == ptr->parent->left) {                    return ptr->parent;                }                ptr = ptr->parent;            }        }    }    return nullptr;}

template<typename T>BinaryTreeNode<T>* invertTree(BinaryTreeNode<T>* root) {    if (root != nullptr) {        invertTree(root->left);  // 处理左子树        invertTree(root->right); // 处理右子树        std::swap(root->left, root->right);  // 交换当前节点的左右节点    }    return root;}

算法的主要思路，先求左子树是否为平衡二叉树和左子树的高度，再求右子树是否为平衡二叉树和右子树的高度，根据左右子树的返回值判断当前树是否平衡和以当前节点为根的树的高度。

这里用tuple来接收来个返回值的组合

#include <tuple>template<typename T>bool isBalance(BinaryTreeNode<T>* head) {    return std::get<0>(isBalance0(head));}/** * 返回值第一个值表示是否是平衡二叉树，第二个值表示树的高度 */template<typename T>std::tuple<bool, int> isBalance0(BinaryTreeNode<T>* head) {    if (head == nullptr) {        return std::make_tuple<bool, int>(true, 0);    }    std::tuple<bool, int> leftBalanceInfo = isBalance0(head->left);    std::tuple<bool, int> rightBalanceInfo = isBalance0(head->right);    bool isBalance = false;    int height = 1;    if (std::get<0>(leftBalanceInfo)  // 左子树平衡，std::get<0>获取第一个元素        && std::get<0>(rightBalanceInfo)   // 右子树平衡        && (::abs(std::get<1>(leftBalanceInfo) - std::get<1>(rightBalanceInfo) <= 1))/*左右高度差不超过1*/) {        isBalance = true;    }    height += std::max(std::get<1>(leftBalanceInfo), std::get<1>(rightBalanceInfo)); // 当前树高度    return std::make_tuple<bool, int>(std::move(isBalance), std::move(height));  // 注意这里的移动语义}

/** * @brief 计算树中所有节点距离的最大值 * 每经过一条边, 距离增加1 *  * @tparam T  * @param head  * @return std::tuple<int, int> [最大距离，树的高度] */template<typename T>int maxDistance(BinaryTreeNode<T>* head) {    return std::get<0>(maxDistance0(head));}template<typename T>std::tuple<int, int> maxDistance0(BinaryTreeNode<T>* head) {    if (head == nullptr) {        return std::make_tuple<int, int>(0, 0);    }    std::tuple<int, int> l = maxDistance0(head->left);    std::tuple<int, int> r = maxDistance0(head->right);    int distance = 0;    int height = 0;    if (head->left != nullptr || head->right != nullptr) {        // ！！！这里需要重点理解        distance = std::max(                            std::max(std::get<0>(l), std::get<0>(r)), /* 左和右中的最大距离 */                            std::get<1>(l) + std::get<1>(r) + 2 /* 左子树和右子树经过当前节点时最大的距离 */                            );        height = std::max(std::get<1>(l), std::get<1>(r)) + 1;    }        return std::make_tuple<int, int>(std::move(distance), std::move(height));}

/** * @brief 获取最低公共祖先 *  * @tparam T  * @param head  * @param node1  * @param node2  * @return int  */template<typename T>BinaryTreeNode<T>* lowestCommonAncestor(BinaryTreeNode<T>* head, BinaryTreeNode<T>* node1, BinaryTreeNode<T>* node2) {    if (head == nullptr) {        return nullptr;    }    if (head == node1 || head == node2) {        return head;    }    BinaryTreeNode<T>* l = lowestCommonAncestor(head->left, node1, node2);    BinaryTreeNode<T>* r = lowestCommonAncestor(head->right, node1, node2);    if (l != nullptr && r != nullptr) return head; // 表示一个节点在head的左边，一个在右边    if (l != nullptr) return l;  // 表示一个节点在当前节点的左边    if (r != nullptr) return r;  // 表示一个节点在当前节点的右边    return nullptr;}/** * @brief 获取节点所在的层 *  * @tparam T  * @param head  * @param node  * @return int  */template<typename T>int levelOf(BinaryTreeNode<T>* head, BinaryTreeNode<T>* node) {    std::queue<std::pair<BinaryTreeNode<T>*, int>> q;    q.push({head, 1});    while (!q.empty()) {        auto n = q.front();        q.pop();        if (n.first == node) return n.second;        if (n.first->left != nullptr) q.push({n.first->left, n.second + 1});        if (n.first->right != nullptr) q.push({n.first->right, n.second + 1});    }    return -1; }/** * @brief 计算两个节点距离, * 首先找到两个节点的最低祖先，然后根据这三个节点的层级，计算两个节点的距离 *  * @tparam T  * @param head  * @param node1  * @param node2  * @return int  */template<typename T>int distanceOf(BinaryTreeNode<T>* head, BinaryTreeNode<T>* node1, BinaryTreeNode<T>* node2) {    BinaryTreeNode<T> *lca = lowestCommonAncestor(head, node1, node2);    int level0 = levelOf(head, lca);    int level1 = levelOf(head, node1);    int level2 = levelOf(head, node2);    return level1 - level0 + level2 - level0;}

这些代码都是听了左程云左神的课后总结的，大家有空也可以去听听他的课，收获很大。