算法训练第二十天|654.最大二叉树、617.合并二叉树、700.二叉搜索树中的搜索、98.验证二叉搜索树

二叉树|654.最大二叉树、617.合并二叉树、700.二叉搜索树中的搜索、98.验证二叉搜索树


654.最大二叉树

自己审题思路

思路和构造二叉树一致

看完代码随想录题解后的收获

思路基本一致

代码:
**
 * 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:
    TreeNode* dfs(vector<int>& nums, int start, int end) {
        if(start >= end) return nullptr;

        int split = start; 
        int  max = INT_MIN;
        for(int i = start; i < end; i++) { // 这里范围缩小到[start, end)
            if(nums[i] > max) {
                max = nums[i];
                split = i;
            }
        }
        TreeNode* root = new TreeNode(max);

        int leftStart = start;
        int leftEnd = split;

        int rightStart = split + 1;
        int rightEnd = end;

        root->left = dfs(nums, leftStart, leftEnd);
        root->right = dfs(nums, rightStart, rightEnd);

        return root;
    }


    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        if(nums.size() == 0) return nullptr;
        return dfs(nums, 0, nums.size());
    }

这里和构造二叉树不同点在于:
寻找根节点(最大值要在[start,end)范围内找),构造二叉树是确定二叉树根节点的数值且数值不重复,所以在整个数组内寻找根节点下标;而该题需要寻找分割数组内的最大值坐标

参考详解


617.合并二叉树

自己审题思路

同步遍历

看完代码随想录题解后的收获

遍历两个树递归返回值问题

代码(修改root1结构):
class Solution {
public:
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
        if(root1 == nullptr) return root2;
        if(root2 == nullptr) return root1;
        
        root1->val += root2->val;
        root1->left = mergeTrees(root1->left,  root2->left);
        root1->right = mergeTrees(root1->right, root2->right);

        return root1;
    }
};

因为是传入了两个树,那么就有两个树遍历的节点root1root2,如果root1 == NULL 了,两个树合并就应该是 root2了(如果root2也为NULL也无所谓,合并之后就是NULL)。
反过来如果root2 == NULL,那么两个数合并就是root1(如果root1也为NULL也无所谓,合并之后就是NULL)。

代码(构建一个新树)

class Solution {
public:
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
        if (t1 == NULL) return t2;
        if (t2 == NULL) return t1;
        // 重新定义新的节点,不修改原有两个树的结构
        TreeNode* root = new TreeNode(0);
        root->val = t1->val + t2->val;
        root->left = mergeTrees(t1->left, t2->left);
        root->right = mergeTrees(t1->right, t2->right);
        return root;
    }
};

参考详解


700.二叉搜索树中的搜索

自己审题思路

利用二叉搜索树特性来遍历二叉树

看完代码随想录题解后的收获

了解二叉搜索树特性

代码:
class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        if(root == nullptr) return nullptr;
        if(root->val == val) return root;

        TreeNode* ans = nullptr;
        if(val < root->val) ans = searchBST(root->left, val);
        if(val > root->val) ans = searchBST(root->right, val);

        return ans;
    }
};

参考详解


98.验证二叉搜索树

自己审题思路

利用二叉搜索树特性来遍历

看完代码随想录题解后的收获

二叉搜索树使用中序遍历

代码:
class Solution {
public:
    long long maxValue = LONG_MIN;
    bool isValidBST(TreeNode* root) {
        if(root == nullptr)  return true;
        

        bool isLeft = isValidBST(root->left);
        if(maxValue < root->val) maxValue = root->val; 
        else return false;
        bool isRight =isValidBST(root->right);

        return isLeft && isRight;
    }
};
代码(前一个节点比较后一个节点(中序)):
class Solution {
public:
    TreeNode* pre = nullptr;
    bool isValidBST(TreeNode* root) {
        if(root == nullptr)  return true;
        

        bool isLeft = isValidBST(root->left);
        if(pre != nullptr && pre->val >= root->val) return false; 
        pre = root;
        bool isRight =isValidBST(root->right);

        return isLeft && isRight;
    }
};
代码(迭代):
class Solution {
public:
    bool isValidBST(TreeNode* root) {
        stack<TreeNode*> st;
        if(root == nullptr) return true;

        TreeNode* cur = root;
        TreeNode* pre = nullptr;
        
        while(!st.empty() || cur != nullptr) {
            while(cur != nullptr) {
                st.push(cur);
                cur = cur->left;
            }
            cur = st.top(); st.pop();
            if(pre != nullptr && pre->val >= cur->val) return false;
            pre = cur;
            cur = cur->right;
        }
        return true;
    }
};
代码(将二叉树转化为有序数组):
class Solution {
private:
    vector<int> vec;
    void traversal(TreeNode* root) {
        if (root == NULL) return;
        traversal(root->left);
        vec.push_back(root->val); // 将二叉搜索树转换为有序数组
        traversal(root->right);
    }
public:
    bool isValidBST(TreeNode* root) {
        vec.clear(); // 不加这句在leetcode上也可以过,但最好加上
        traversal(root);
        for (int i = 1; i < vec.size(); i++) {
            // 注意要小于等于,搜索树里不能有相同元素
            if (vec[i] <= vec[i - 1]) return false;
        }
        return true;
    }
};

参考详解


最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 216,240评论 6 498
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 92,328评论 3 392
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 162,182评论 0 353
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 58,121评论 1 292
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 67,135评论 6 388
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 51,093评论 1 295
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 40,013评论 3 417
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 38,854评论 0 273
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 45,295评论 1 310
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,513评论 2 332
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,678评论 1 348
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 35,398评论 5 343
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 40,989评论 3 325
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,636评论 0 22
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,801评论 1 268
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 47,657评论 2 368
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 44,558评论 2 352

推荐阅读更多精彩内容