视频链接

主要就是两个个,非递归中序遍历和花式建树

验证二叉搜索树 https://leetcode-cn.com/problems/Validate-Binary-Search-Tree/

  1. class Solution {
  2. public:
  3. bool isValidBST(TreeNode* root) {
  4. typedef long long ll;
  5. function<bool (TreeNode*, ll, ll)> f = [&](TreeNode *root, ll min_val, ll max_val) -> bool {
  6. if (!root) return true;
  7. if (root->val >= min_val && root->val <= max_val) return f(root->left, min_val, root->val - 1ll) && f(root->right, root->val + 1ll, max_val);
  8. return false;
  9. };
  10. return f(root, INT_MIN, INT_MAX);
  11. }
  12. };

大概思路:确定每棵树的 值范围


二叉树的中序遍历 https://leetcode-cn.com/problems/Binary-Tree-Inorder-Traversal/

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        auto s = stack<TreeNode*>();
        auto vec = vector<int>();
        auto p = root;
        while (p || s.size()) {
            while (p) s.push(p), p = p->left;
            p = s.top(); s.pop();
            vec.push_back(p->val);
            p = p->right;
        }

        return vec;
    }
};

二叉树的后序遍历 https://leetcode-cn.com/problems/binary-tree-postorder-traversal/

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        stack<TreeNode*> s;
        vector<int> ans;
        auto p = root;
        while (p || s.size()) {
            while (p) {
                s.push(p);
                ans.push_back(p->val);
                p = p->right;
            }
            p = s.top(); s.pop();
            p = p->left;
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }
};

二叉树的前序遍历 https://leetcode-cn.com/problems/binary-tree-preorder-traversal/

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> ans;
        auto p = root;
        stack<TreeNode*> s;
        while (p || s.size()) {
            while (p) {
                s.push(p);
                p = p->left;
            }
            p = s.top(); s.pop();
            p = p->right;
        }
        return ans;
    }
};

三种遍历思路都差不多,利用 stack 去存递归回来会访问的点,后序遍历有点特殊,整个结果反了一下


对称二叉树 https://leetcode-cn.com/problems/Symmetric-Tree/

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if (!root) return true;
        stack<TreeNode*> s1, s2;
        auto p = root->left, q = root->right;
        while ( (p || s1.size()) && (q || s2.size()) ) {
            while (p && q) {
                s1.push(p); p = p->left;
                s2.push(q); q = q->right;
            }
            if (p || q) return false;
            p = s1.top(); s1.pop();
            q = s2.top(); s2.pop();
            if (p->val != q->val) return false;
            p = p->right;
            q = q->left;
        }
        return true;
    }
    bool f(TreeNode *left, TreeNode *right) {
        if (!left || !right) return left == right;
        return left->val == right->val && f(left->left, right->right) && f(left->right, right->left);
    }
};

大概思路:
递归写法比较简单
非递归写法是这样,还是利用前面非递归实现树的遍历去做,只是左右两边反着来,左边是先左,右边是先右


从前序与中序遍历序列构造二叉树 https://leetcode-cn.com/problems/Construct-Binary-Tree-from-Preorder-and-Inorder-Traversal/

class Solution {
public:
    unordered_map<int, int> m;
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        // 前序遍历找根,中序遍历确定子树
        int n = preorder.size();
        for (int i = 0; i < n; i++) m[inorder[i]] = i;

        return f(preorder, 0, 0, preorder.size() - 1);
    }
    TreeNode* f(const vector<int> & pre_o, int p, int l, int r) {
        if (l > r) return NULL;
        auto root = new TreeNode(pre_o[p]);
        int pos = m[pre_o[p]];
        root->left = f(pre_o, p + 1, l, pos - 1);
        root->right = f(pre_o, p + pos - l + 1,pos + 1, r);
        return root;
    }
};

大概思路:前序遍历时,子树一定在根右边,中序遍历时,左子树在根左边,右子树在根右边
用哈希表优化一下,这样在中序遍历里找根时,可以不用扫过去,使总的复杂度是 O(N)


二叉树的层次遍历 https://leetcode-cn.com/problems/Binary-Tree-Level-Order-Traversal/

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> ans;
        queue<TreeNode*> q;
        if (root) q.push(root);
        while (q.size()) {
            int len = q.size();
            vector<int> sub;
            while (len--) {
                auto node = q.front(); q.pop();
                sub.push_back(node->val);
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
            ans.push_back(sub);
        }
        return ans;
    }
};

大概思路:bfs过去就行,不过可以用一个小技巧,每次拿一层节点出来,从而少几个变量
队列里一共有 N 个元素,说明这一层只需要扩展 N 次,每一层都按照这样弄,自然就是一次扩展一层。


二叉树的最近公共祖先 https://leetcode-cn.com/problems/Lowest-Common-Ancestor-of-a-Binary-Tree/

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (!root) return root;
        if (root == p || root == q) return root;
        auto left = lowestCommonAncestor(root->left, p, q);
        auto right = lowestCommonAncestor(root->right, p, q);
        if (!left) return right;
        if (!right) return left;
        return root;
        // 总共有三种情况
        // p 是 q 的父节点
        // q 是 p 的父节点
        // p 和 q 有一个最近公共节点
        /*
        1 和 2 都能表现为 在一边找到了 p/q,而另一边为空
        3 能表现为,在两边各自找到了 p/q,所以答案一定是 root
        */
    }
};

大概思路:由于并不没有什么时间复杂度的限制,所以简单点写就好。
一棵树的最近公共祖先:

  • 在左子树上
  • 在右子树上
  • 根节点

如果一棵树 根节点p || 根节点q,那么返回根节点
如果一棵树,左子树递归解决,记作 left,右子树递归解决,记作 right
如果 left 和 right 只有一个为空,那么另一个一定不是空的点一定是最近公共祖先
如果 left 和 right 都为空,那么返回根节点


二叉树的直径 https://leetcode-cn.com/problems/Diameter-of-Binary-Tree/

class Solution {
public:
    int ans = 0;

    int diameterOfBinaryTree(TreeNode* root) {
        dfs(root);
        return ans;
    }
    int dfs(TreeNode *root) {
        if (!root) return 0;
        int l = dfs(root->left);
        int r = dfs(root->right);
        ans = max(ans, l + r);
        return max(l, r) + 1;
    }
};

大概思路,枚举当前子树的最大值,更新答案,并把当前子树的最大深度返回上一层


二叉树中的最大路径和 https://leetcode-cn.com/problems/Binary-Tree-Maximum-Path-Sum/

class Solution {
public:
    int ans = INT_MIN;
    int maxPathSum(TreeNode* root) {
        dfs(root);
        return ans;
    }
    int dfs(TreeNode *root) {
        if (!root) return 0;
        int left = dfs(root->left);
        int right = dfs(root->right);
        ans = max(ans, left + right + root->val);
        return max(0, max(left, right) + root->val);
    }
};

大概思路:和上题思路一样,不过这里有一点要注意。如果当前子树的最大值小于 0,那么就不用往上返回了。上面不会用到。


二叉搜索树迭代器 https://leetcode-cn.com/problems/Binary-Search-Tree-Iterator/

class BSTIterator {
public:
    stack<TreeNode*> s;
    TreeNode *p;
    BSTIterator(TreeNode* root) {
        p = root;
        while (p) {
            s.push(p);
            p = p->left;
        }
    }

    /** @return the next smallest number */
    int next() {
        p = s.top(); s.pop();
        int val = p->val;
        p = p->right;
        while (p) {
            s.push(p);
            p = p->left;
        }
        return val;
    }

    /** @return whether we have a next smallest number */
    bool hasNext() {
        return s.size();
    }
};

大概思路:和上面一样,不过是把非递归遍历分开了写


二叉树的序列化与反序列化 https://leetcode-cn.com/problems/Serialize-and-Deserialize-Binary-Tree/

class Codec {
public:
    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        string ans;
        dfs(root, ans);
        // cout << ans << endl;
        return ans.substr(1);
    }
    void dfs(TreeNode *root, string &ans) {
        if (!root) {
            ans += ",#";
            return;
        }
        ans += "," + to_string(root->val);
        dfs(root->left, ans);
        dfs(root->right, ans);
    }
    int myatoi(int &pos, const string & str) {
        bool isMinus = false;
        int s = 0;
        if (str[pos] == '-') isMinus = true, pos++;
        while (str[pos] != ',') {
            s = s * 10 + str[pos] - '0';
            pos++;
        }
        pos++;
        return isMinus ? s * -1 : s;
    }

    TreeNode* dfs2(int &pos, const string & data) {
        if (data[pos] == '#') {
            pos += 2;
            return NULL;
        }
        auto head = new TreeNode(myatoi(pos, data));
        head->left = dfs2(pos, data);
        head->right = dfs2(pos, data);
        return head;
    }
    TreeNode* deserialize(string data) {
        int pos = 0;
        return dfs2(pos, data);
    }
};

大概思路:虽然前序遍历不能确认一棵树,但前序遍历加记录空节点可以
有一点需要注意,传进函数里的 pos 是能动的,使得下一个调用完下一个函数之后,上一层可以利用当前层的信息,直接往下,节省时间。