二叉树 LeetCode 刷题小结(七)

在上节的基础上，本节我们将继续汇总一些 LeetCode 有关二叉树的题。

---

---

接着上节，我们继续汇总二叉树相关的例题。
所有题均来自于leetcode。

二叉树剪枝

给定二叉树根结点 root ，此外树的每个结点的值要么是 0，要么是 1。

返回移除了所有不包含 1 的子树的原二叉树。

( 节点 X 的子树为 X 本身，以及所有 X 的后代。)

图片.png 图片.png

移除的条件是这个子树含有0，递归左右子树，如果满足条件，对应的指针域赋值为空即可。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* pruneTree(TreeNode* root) {
        if(fun(root)){
            return root;
        }else{
            return NULL;
        }
    }
    bool fun(TreeNode* tree){
        if(tree==NULL){
            return false;
        }
        bool l=fun(tree->left);
        bool r=fun(tree->right);
        if(!l){
            tree->left=NULL;
        }
        if(!r){
            tree->right=NULL;
        }
        return tree->val==1||l||r;
    }
};

最长同值路径

给定一个二叉树，找到最长的路径，这个路径中的每个节点具有相同值。 这条路径可以经过也可以不经过根节点。

注意：两个节点之间的路径长度由它们之间的边数表示。

图片.png

在递归过程中，如果其左(右)子树的节点域等于根节点的节点域，说明这可能是一条路径，递归左右子树，同时记录路径长度。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int res;
    int longestUnivaluePath(TreeNode* root) {
        res=0;
        fun(root);
        return res;
    }
    int fun(TreeNode* root){
        if(root==NULL){
            return 0;
        }
        int l=fun(root->left);
        int r=fun(root->right);
        int ll=0,rr=0;
        if(root->left!=NULL && root->left->val==root->val){
            ll+=l+1;
        }
        if(root->right!=NULL && root->right->val==root->val){
            rr+=r+1;
        }
        res=max(res,rr+ll);
        return max(ll,rr);
    }
};

二叉树最大宽度

给定一个二叉树，编写一个函数来获取这个树的最大宽度。树的宽度是所有层中的最大宽度。这个二叉树与满二叉树（full binary tree）结构相同，但一些节点为空。

每一层的宽度被定义为两个端点（该层最左和最右的非空节点，两端点间的null节点也计入长度）之间的长度。

bfs做法，只不过稍微有一点点区别，我们需要使用双端队列，入节点方式略有不同。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int widthOfBinaryTree(TreeNode* root) {
        int ans=0;
        if(!root){
            return ans;
        }
        TreeNode* tmp=nullptr;
        deque<TreeNode*> d;
        d.push_back(root);
        while(!d.empty()){
            //判断队列是否为空
            while(!d.empty() && !d.front()){
                d.pop_front();
            }
            while(!d.empty() && !d.back()){
                d.pop_back();
            }
            int n=d.size();
            if(!n){
                break;
            }
            ans=max(ans,n);
            while(n--){
                tmp=d.front();
                d.pop_front();
                d.push_back(tmp==NULL ? NULL:tmp->left);
                d.push_back(tmp==NULL ? NULL:tmp->right);
            }
        }
        
        return ans;
    }
};

根据二叉树创建字符串

你需要采用前序遍历的方式，将一个二叉树转换成一个由括号和整数组成的字符串。

空节点则用一对空括号 "()" 表示。而且你需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对。

图片.png

本题需要考虑递归过程中左右子树的处理情况，解决好这个问题，就不难了。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    string tree2str(TreeNode* t) {
        if(!t){
            return "";
        }
        if(!t->left&&!t->right){
            return to_string(t->val) +"";
        }
        if(!t->right){
            return to_string(t->val)+"("+tree2str(t->left)+")";
        }
        return to_string(t->val)+"("+tree2str(t->left)+")("+tree2str(t->right)+")";
    }
};