树算法题目集合

leetcode199 二叉树的右视图

给定一个二叉树的根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

leetcode230 二叉搜索树中第 K 小的元素

给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 小的元素（从 1 开始计数）。

题解

root->left->val < root->val < root->right->val

int kthSmallest(TreeNode* root, int k) {
    int count = 0;
    stack<TreeNode*> treeStack;
    treeStack.push(root);
    while (treeStack.size() > 0) {
        TreeNode* base = treeStack.top();
        if (base->left == nullptr) {
            count ++;
            treeStack.pop();
            if (count == k) {
                return base->val;
            }
            if (base->right != nullptr) {
                treeStack.push(base->right);
                continue;
            }
        }
        else {
            treeStack.push(base->left);
            base->left = nullptr;
            continue;
        }
    }
    return 0;
}

leetcode148 排序链表

给你链表的头结点 head ，请将其按升序排列并返回排序后的链表

题解

归并排序链表，递归分治，子链表按序合并

树和算式

Leetcode 题解

各种表达式没有本质区别，他们其实是同一个语法树，只是遍历方式不同而得到的不同式子；是一个事物的一体多面，只不过是从不同角度观察罢了。

中缀表达式是其对应的语法树的中序遍历； 后缀表达式是其对应的语法树的后序遍历； 前缀表达式是其对应的语法树的前序遍历；

leetcode105 从前序与中序遍历序列构造二叉树

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

题解

前序遍历提供根节点，中序遍历提供子树结构

Leetcode 题解

class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        this->preorder = preorder;
        for(int i = 0; i < inorder.size(); i++)
            dic[inorder[i]] = i;
        return recur(0, 0, inorder.size() - 1);
    }
private:
    vector<int> preorder;
    unordered_map<int, int> dic;
    TreeNode* recur(int root, int left, int right) {
        if (left > right) return nullptr;                        // 递归终止
        TreeNode* node = new TreeNode(preorder[root]);          // 建立根节点
        int i = dic[preorder[root]];                            // 划分根节点、左子树、右子树
        node->left = recur(root + 1, left, i - 1);              // 开启左子树递归
        node->right = recur(root + i - left + 1, i + 1, right); // 开启右子树递归
        return node;                                            // 回溯返回根节点
    }
};

leetcode94 树的中序遍历

中序遍历

使用栈数据结构控制遍历节点顺序，类比递归调用的栈

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> ret;
        if (root == nullptr) return ret;
        stack<TreeNode*> tree;
        tree.push(root);
        while (! tree.empty()) {
            TreeNode* top = tree.top();
            if (top->left != nullptr) {
                tree.push(top->left);
                top->left = nullptr;
                continue;
            }
            ret.push_back(top->val);
            tree.pop();
            if (top->right != nullptr) {
                tree.push(top->right);
            }
        }
        return ret;
    }
};

通过递归重复根节点操作

leetcode124 二叉树中的最大路径和

路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。 路径和 是路径中各节点值的总和。 给定一个二叉树的根节点 root ，返回其 最大路径和，即所有路径上节点值之和的最大值。

思路

共有两种路径，一种是左右节点跨越根的环形路径，一种为父子节点的直线路径 在递归的过程中，若子树的值为负，对最大和无贡献，可置为 0，计算左右子树和根节点的和，更新当前最大值 注意递归的返回值需包含根节点，已构成完整路径

class Solution {
private:
    int maxSum = 0;
public:
    int getMax(TreeNode_ root) {
        if (! root) return 0;
        int left = max(0, getMax(root->left));
        int right = max(0, getMax(root->right));
        maxSum = max(maxSum, root->val + left + right);
        return root->val + max(left, right);
    }

    int maxPathSum(TreeNode* root) {
        maxSum = INT_MIN;
        getMax(root);
        return maxSum;
    }

};

完全二叉树

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

leetcode222 完全二叉树的节点个数

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

比较有趣的思路：参考

比较左右子树高度，若相等则左子树必为满树，若不相等则右子树必为满树

class Solution {
public:

    // 计算子树高度
    int getHeight(TreeNode* root) {
        if (! root) return 0;
        return 1 + max(getHeight(root->left), getHeight(root->right));
    }

    // 计算子树节点数
    int countNodes(TreeNode* root) {
        if (! root) return 0;
        int leftHeight = getHeight(root->left);
        int rightHeight = getHeight(root->right);
        // 比较子树高度
        if (leftHeight == rightHeight) {
            // 递归计算子树节点数，累加完全树节点数
            return countNodes(root->right) + (1 << leftHeight);
        }
        else {
            return countNodes(root->left) + (1 << rightHeight);
        }
    }
};