单词搜索

212. 单词搜索 II

思路:

虽然明明知道硬写一定会,超时,但还是写了一个。

超时后考虑什么优化:自然想到了字典树。不过没有想透彻:

  • 用字典树构造dfs遍历的路径,❌ :dfs搜索的路径不需要被查询,因为只出现一次

  • 正确做法:用字典树存储所有words,方便查询。或者进一步的,在dfs过程中,可以直接用字典树进行搜索剪枝。

    Orz

Read more

之字形标记

1104. 二叉树寻路

思路

思路其实很清晰,翻转出层序的下标,在遍历的时候,把层序下标翻转回之字下标即可。

良好的编程习惯其实蛮重要的,每个变量都有自己的用处。良好的代码对后续的修改友善的。

Read more

二叉树中距离为K的节点

思路

这题还是有点点复杂的,距离为K的节点,完全可以分为两类,target节点构成树的K-dis节点,和其路径经过target祖父节点的节点。分类搜索即可,考虑到后者需要定点采集,所以用回溯的方式获取。

Read more

二叉树的两个错误节点

CD169 找到搜索二叉树中两个错误的节点

如果两个节点交换,那么在中序遍历里就有至少一次降序,可能有两个相邻的节点交换,或者两个不相邻的节点交换,产生一个或两次降序。

Read more

二叉树累加和的最长路径

CD165 在二叉树中找到累加和为指定值的最长路径长度

写的好心酸, 明明只有有类似的题目接触到。又是没思考就动手

  • 先静态化构造二叉树(不要嫌麻烦,一题写好了所有题目都可以用)

  • 前序遍历节点,

    • 记录根节点到当前节点的综合newadd,只记录最短长度的newadd路径。
    • 同时判断,newadd - target之和是否有在当前遍历路径下,是否存在从根节点到同路径的某个节点连成的路径。
    • 最后回溯时,为了下次遍历路径不受这里遍历数据影响,消减掉当次遍历时候设置新路径长度。
Read more

面试题 04.09. BST Sequences LCCI

面试题 04.09. BST Sequences LCCI

懵树下你和我,快乐刷刷题

思路

二叉树的构建,是从根节点开始的,每构建的一个节点,就添加了一个可能两个新扩展节点,我们可以在其中任意选择一个节点新构建,如此递归下去,完成整棵树的构建。

那么,我们需要模拟整棵树的构建遍历过程,用deque存储每次构建时可以选择的节点,递归构造。如果deque为空,说明建构完成,把记录构建顺序的path加入答案即可。建构完成后回溯进行下一个节点的构建。

Read more

331. Verify Preorder Serialization of a Binary Tree

331. Verify Preorder Serialization of a Binary Tree

思路:

  1. 按照字符串提供的数据按前序遍历伪建树,如果用完了所有字符就建树成功。
  2. 前序遍历允许我们的用栈记录当前节点以及之前节点应该生长的分支数,比如碰到一个数字,上一个节点的减一分支数,插入一个当点节点的分支数2。遍历过程中,栈为空或者遍历后,字符数还有剩余,显然建树失败。
Read more

109. Convert Sorted List to Binary Search Tree

思路:

链表实际上给出的是二叉树前序的结果,因为AVL树任意左右子树高度不超过1,我们可以选择链表中点,并将链表的长度尽可能一样长的两部分划分到左右子树,所以高度性质可以维持住。

在中序遍历链表,控制子树长度,即可构建符合题意的AVL树。

Read more

450. Delete Node in a BST

思路:

删除一个只有一个子节点,或者没有子节点的节点,比较简单。

删除有两个子节点的节点A,需要把找一个比A大的最小子节点B来替换该A。那么同时也需要递归的删除节点B

Read more

1609. Even Odd Tree

思路:

层序遍历。记录边界即可。

代码:


/**
 * 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:
    
    bool isEvenOddTree(TreeNode* root) {
        if(root == nullptr ) return false;
        queue<TreeNode *> que;
        vector<int> a;
        int level = 0, num = 1, nextn = 0;;
        que.push(root);
        while(!que.empty()){
            TreeNode *t = que.front();
            que.pop();
            a.push_back(t->val);
            num--;
            if(t->left){
                que.push(t->left);
                nextn++;
            }
            if(t->right){
                que.push(t->right);
                nextn++;            
            }            
            if(num == 0){
                num = nextn;
                nextn = 0;
                int flag = 1;
                if(a.size() < 1) continue;

                if(level & 1){
                    for(int i = 1; i < a.size(); i++){
                        if(a[i] >= a[i - 1] || a[i]%2 == 1 )
                            flag = 0;
                    }
                    if(a[0]%2 == 1) flag = 0;
                }
                else{
                    for(int i = 1; i < a.size(); i++){
                        if(a[i] <= a[i - 1] || a[i]%2 == 0)
                            flag = 0;
                    }                
                    if(a[0]%2 == 0) flag = 0;

                }
           
                a.clear();
                level ++;
                if(!flag) return false;
            }   
        }
        return true;
    }
};

654. 最大二叉树

一个基础的递归建树就可以解决。

以递归的思想处理每一个新数组,先找出最大值所在并以此值一分数组为2个数组,同时递归建树即可。

Note:注意边界错误,如right到底没有没值

/**
 * 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* constructMaximumBinaryTree(vector<int>& nums) {
        return constructBT(nums, 0, nums.size() - 1);
        
    }
    TreeNode* constructBT(vector<int>& nums, int left, int right){
        if(left > right)
            return NULL;
        
        int index = left, nmax = nums[left];
        for(int i = left + 1; i <= right; i++){
            if(nmax < nums[i]){
                nmax = nums[i];
                index = i;
            }
        }
        TreeNode* root = new TreeNode(nmax);
        root->left = constructBT(nums, left, index - 1);
        root->right  = constructBT(nums, index + 1, right);
        return root;
    }
    
    

};