LeetCode专题树

只需要遍历到每一个结点即可，然后交换左右两个孩子结点。

/**
 * 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* invertTree(TreeNode* root) {
        if(root==NULL){
            return NULL;
        }
        TreeNode* tmp = invertTree(root->left);
        root->left = invertTree(root->right);
        root->right = tmp;
        return root;
    }
};

235.二叉搜索树的最近公共祖先 ★★★

LCA最近公共祖先，有点意思，第一次写的超级垃圾的代码108ms，103.5MB。

/**
 * 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:
    vector<vector<TreeNode*>> helper;
    void DFS(TreeNode* root,vector<TreeNode*> path,TreeNode* target){
        if(root==NULL){
            return;
        }
        path.push_back(root);
        if(root==target){
            helper.push_back(path);
            return;
        }
        if(root->left!=NULL){
            DFS(root->left,path,target);
        }
        if(root->right!=NULL){
            DFS(root->right,path,target);
        }   
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root==NULL){
            return NULL;
        }
        vector<TreeNode*> path_p;
        DFS(root,path_p,p);
        DFS(root,path_p,q);
        int i = 0;
        int j = 0;
        while(i<helper[0].size()&&j<helper[1].size()){
            cout<<helper[0][i]->val<< " " <<helper[1][j]->val<<endl;
            if(helper[0][i]==helper[1][j]){
                i++,j++;
            }else{
                break;
            }
        }
        return helper[0][i-1];
    }
};

二叉搜索树BST的性质
1. 节点 N 左子树上的所有节点的值都小于等于节点 N 的值
2. 节点 N 右子树上的所有节点的值都大于等于节点 N 的值
3. 子树和右子树也都是 BST
算法
1. 从根节点开始遍历树
2. 如果节点 p 和节点 q 都在右子树上，那么以右孩子为根节点继续 (a) 的操作
3. 如果节点 p 和节点 q 都在左子树上，那么以左孩子为根节点继续 (a) 的操作
4. 如果条件 2 和条件 3 都不成立，这就意味着我们已经找到节 p 和节点 q 的 LCA 了
在左右子树上，则root.val - p.val和root.val - q.val异号

同在左/右子树，则同号，分别递归地遍历左/右子树

该算法得到的性能是36ms，23.5MB

/**
 * 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* lca = NULL;
    void LCA(TreeNode* root, TreeNode*p, TreeNode* q){
        if((root->val - p->val)*(root->val - q->val) <= 0){
            lca = root;//如果p,q分别再左右子树上，则root就是lca
        }else if(root->val < p->val && root->val < q->val){
            LCA(root->right, p, q);
        }else{
            LCA(root->left, p, q);
        }
    }

    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        // 题目的意思是树不空
        // if (!root) return nullptr;
        LCA(root, p, q);
        return lca;
    }
};

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(!root) return NULL;
        if(q -> val > root -> val && p -> val > root -> val)    
            return lowestCommonAncestor(root -> right, p, q);// 都在root的右边
        if(q -> val < root -> val && p -> val < root -> val)    
            return lowestCommonAncestor(root -> left, p, q); // 都在root的左边
        return root; // 若分布在root的两侧，说明root为最近公共祖先
    }
};

进阶：二叉树 - 无左小右大的性质，需要全盘搜索
1. 遇到指定节点，直接返回root，无需往下搜寻。
2. 向左右子树遍历，返回包含指定节点的子树。
3. 若左右子树都包含指定节点，则当前root为最近公共祖先。
自底向上遍历结点，一旦遇到结点等于p或者q，则将其向上传递给它的父结点。父结点会判断它的左右子树是否都包含其中一个结点，如果是，则父结点一定是这两个节点p和q的LCA，传递父结点到root。如果不是，我们向上传递其中的包含结点p或者q的子结点，或者NULL(如果子结点不包含任何一个)。该方法时间复杂度为O(N)。

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(!root || root == p || root == q ) return root;
        // ↓ l(r)=NULL,左(右)子树不包含p或q;l(r)=p或q,左(右)子树包含有p或q
        TreeNode* l = lowestCommonAncestor(root -> left, p , q);
        TreeNode* r = lowestCommonAncestor(root -> right, p, q);
        if(l && r) return root; // 如果p和q位于不同的子树,根即为LCA
        return l ? l : r; 
        // ↑ p和q在当前以root为根的相同的子树中(即左右子树)
    }
};

404.左叶子之和

算法思路对任意一个节点，它只需要做两件事； 1、判断它的左孩子是不是左叶子； 2、让它的左孩子和右孩子分别向它汇报，以该孩子为根的sumOfLeftLeaves；最后简单相加即可，很典型的递归算法。

/**
* 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 sumOfLeftLeaves(TreeNode* root) {
        if(root==NULL)return 0;
        int left_sum = 0;
        if(root->left!=NULL){
            if(root->left->left==NULL && root->left->right==NULL){
                left_sum += root->left->val;//root->left是左叶子结点
            } else {
                left_sum += sumOfLeftLeaves(root->left);
            }
        }
        if(root->right!=NULL){
            left_sum += sumOfLeftLeaves(root->right);
        }
        return left_sum;
    }
};

我的想法是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 sumOfLeftLeaves(TreeNode* root) {
        if(root==NULL)return 0;
        queue< pair<TreeNode* , int> > que;
        que.push(make_pair(root,-1));//0左1右，root默认为-1
        int left_sum = 0;
        while(!que.empty()){
            pair<TreeNode*, int> hp = que.front();
            que.pop();
            TreeNode* p = hp.first;
            if(p->left==NULL && p->right==NULL && hp.second==0){
                left_sum += p->val;
            }
            if(p->left!=NULL){
                que.push(make_pair(p->left,0));
            }
            if(p->right!=NULL){
                que.push(make_pair(p->right,1));
            }
        }

        return left_sum;
    }
};

501.二叉搜索树中的众数

不使用额外空间的方法（递归的隐式栈开销忽略不计），和一开始想的方式很类似，但是用递归的方式实现。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
 //前序遍历(Preorder transversal),中序遍历(Inorder transversal)以及后序遍历(Postorder transversal)
class Solution {
public:
    vector<int> findMode(TreeNode* root) {
        Inorder(root);
        return ans;
    }
	// void Inorder(TreeNode* root,TreeNode*& pre)引用传递
    void Inorder(TreeNode* root){
        // 这里我犯了一个错误，pre必须是全局的pre，
        // 要按照引用传递或者设置全局变量，否则回溯的时候pre不会更新
        if(root==NULL)return;
        Inorder(root->left);
        if(pre!=NULL && root->val==pre->val){
            cur_cnt ++;
        }else{
            cur_cnt = 1;
        }
        
        if(max_cnt < cur_cnt){   
            max_cnt = cur_cnt;
            ans.clear();
            ans.push_back(root->val);
        }else if(max_cnt==cur_cnt){
            ans.push_back(root->val);
        }
        pre = root;
        Inorder(root->right);
    }
private:
    vector<int> ans;
    int max_cnt = 0;
    int cur_cnt = 1;
    TreeNode* pre = NULL;//记录中序遍历过程中当前结点的前驱结点
};

这个开销太大了，是最直接的做法，即原问题等价于求一个单调不减数列的众数。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
 //前序遍历(Preorder transversal),中序遍历(Inorder transversal)以及后序遍历(Postorder transversal)
class Solution {
public:
    vector<int> inorder;
    void DFS(TreeNode* root){
        if(root==NULL)return;
        DFS(root->left);
        inorder.push_back(root->val);
        DFS(root->right);
    }
    vector<int> findMode(TreeNode* root) {
        DFS(root);
        vector<int> ans;
        int max_cnt = 0,cnt = 1;
        int size = inorder.size();
        if(size==0)return ans;
        int pre_val=inorder[0];
        for(int i=1;i<=size;i++){
            if(i<size && inorder[i]==inorder[i-1]){
                cnt ++;
            }else{
                if(max_cnt < cnt){
                    max_cnt = cnt;
                    ans.clear();
                    ans.push_back(inorder[i-1]);
                }else if(max_cnt==cnt){
                    ans.push_back(inorder[i-1]);
                }
                cnt = 1;
            }
        }
        return ans;
    }
};

530.二叉搜索树的最小绝对差

/**
 * 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 getMinimumDifference(TreeNode* root) {
        getMin(root);
        return ans;
    }
    void getMin(TreeNode* root){
        if(!root) return;
        getMin(root->left);
        if(pre!=NULL && root->val - pre->val < ans){
            ans = root->val - pre->val;
        }
        pre = root;
        getMin(root->right);
    }
private:
    const int INF = 0x3f3f3f3f;
    int ans = INF;
    TreeNode* pre = NULL;
};

/**
 * 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:
    void dfs(TreeNode* root, int& prev, int& res) {
        if (root == NULL) return;
        dfs(root->left, prev, res);
        if (prev >= 0) res = min(res, root->val - prev);
        prev = root->val;
        dfs(root->right, prev, res);
    }
    int getMinimumDifference(TreeNode* root) {
        int prev = -1;
        int res = INT_MAX;
        dfs(root, prev, res);
        return res;
    }
};

二叉搜索树的绝杀方式

538.把二叉搜索树转换为累加树

aha，一次AC，核心还是"中序遍历"，只不过该问需要从最右结点开始反向中序遍历，利用BST的特性（见235.LCA）当前结点的值加上大于当前结点"右侧"结点的值（右边的一定大）。

/**
 * 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* convertBST(TreeNode* root) {
        buildGT(root);
        return root;
    }

    void buildGT(TreeNode* root){
        if(root==NULL)return;
        buildGT(root->right);
        if(pre!=NULL){
            root->val += pre->val;
        }
        pre = root;
        buildGT(root->left);
    }

private:
    TreeNode* pre = NULL;//记录反向中序遍历的"前驱"结点
};

543.二叉树的直径

数的直径即求两节点间最大距离，即转化可递归解决的问题：

1、不经过root，最长路径子在左子树上

2、不经过root，最长路径子在右子树上

3、经过root，最长路径为左右子树的最大高度之和。

/**
 * 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 diameterOfBinaryTree(TreeNode* root) {
        maxDepth(root);
        return max_diameter;
    }

    int maxDepth(TreeNode* root){
        if(root==NULL) return 0;
        int dL = maxDepth(root->left);
        int dR = maxDepth(root->right);
        max_diameter = max(max_diameter, dL+dR);
        return max(dL,dR) + 1;
    }

private:
    int max_diameter = 0;
};

563.二叉树的坡度

/**
 * 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 findTilt(TreeNode* root) {
        getSum(root);
        return tilt;
    }

    int getSum(TreeNode* root) {
        if(root==NULL)return 0;
        int L = getSum(root->left);
        int R = getSum(root->right);
        tilt += abs(L - R);
        return L + R + root->val;
    }

private:
    int tilt = 0;
};

572.另一个树的子树 ★★★★

Donald Trump： Nobody knows SIMPLICITY better than me, noboday.

官方题解，从暴力搜索匹配到字符串匹配KMP，再到树的hash，着实厉害。

最简单的匹配方法

/**
 * 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 isSubtree(TreeNode* s, TreeNode* t) {
        if(s==NULL)return false; //主树为空时，返回false，避免使用空指针
        return isSame(s,t) || isSubtree(s->left,t) || isSubtree(s->right,t);
    }

    bool isSame(TreeNode* s, TreeNode* t){
        if(s==NULL && t==NULL) return true;
        if(s==NULL || t==NULL || s->val!=t->val) return false;
        return isSame(s->left,t->left) && isSame(s->right,t->right);
    }

};

589.N叉树的前序遍历

树的遍历合集

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
public:
    vector<int> ans;
    vector<int> preorder(Node* root) {
        traverse(root);
        return ans;
    }

    void traverse(Node* root){
        if(root==NULL)return;
        ans.push_back(root->val);
        for(auto e : root->children){
            traverse(e);
        }
    }
};

迭代法

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
public:
    vector<int> preorder(Node* root) {
        vector<int> ans;
        stack<Node*> st;
        // if(root==NULL)return ans;
        st.push(root);
        while(!st.empty()){
            Node* p = st.top();
            st.pop();
            if(p!=NULL){
                ans.push_back(p->val);
                for(int i=p->children.size()-1;i>=0;i--){
                    st.push(p->children[i]);
                }
            }  
        }
        return ans;
    }
};

590.N叉树的后序遍历

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
public:
    vector<int> ans;
    vector<int> postorder(Node* root) {
        traverse(root);
        return ans;
    }

    void traverse(Node* root){
        if(root==NULL) return;
        for(auto e:root->children){
            traverse(e);
        }
        ans.push_back(root->val);
    }
};

606.根据二叉树创建字符串

题目的意思是子节点需要用()来包裹。举例来说，二叉树[root,left,right]，则转换为root(left)(right)。如果只有left为空节点，则输出root()(right)；如果只有right为空节点则可以忽略右节点的()，输出为root(left)。

/**
 * 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==NULL) return "";
        string ans = "";
        string L = tree2str(t->left);
        string R = tree2str(t->right);
        if(t->left==NULL && t->right==NULL) {
            ans = to_string(t->val);
        } else if(t->left!=NULL && t->right==NULL) {
            ans = to_string(t->val) + "(" + L + ")";
        }else {
            ans = to_string(t->val) + "(" + L + ")" + "(" + R + ")";
        } 
        return ans;
    }
};

617.合并二叉树 ★★

一开始没想到的是孩子为空的时候啥也不用做，直接连接即可。

我们可以对这两棵树同时进行前序遍历，并将对应的节点进行合并。在遍历时，如果两棵树的当前节点均不为空，我们就将它们的值进行相加，并对它们的左孩子和右孩子进行递归合并；如果其中有一棵树为空，那么我们返回另一颗树作为结果；如果两棵树均为空，此时返回任意一棵树均可（因为都是空）。

/**
 * 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* mergeTrees(TreeNode* t1, TreeNode* t2) {
        TreeNode* root = t1 ? t1 : t2;
        if(t1&&t2){
            t1->val += t2->val;
            t1->left = mergeTrees(t1->left,t2->left);
            t1->right = mergeTrees(t1->right,t2->right);
        }
        return root;
    }
};

非递归的实现：如果t1和t2非空，则将其val求和并赋值给t1，然后考虑左右孩子，（以左孩为例）如果t1左孩子为空，则将t2的左孩子作为t1的左孩子，如果t1左孩子非空，则将结点入栈/队，两者皆空则无操作（上述，右孩子同理）；如果t1为空，则返回t2（无论t2是否为空，不影响结果），否则返回t1。

/**
 * 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* mergeTrees(TreeNode* t1, TreeNode* t2) {
        //判断t1空的情况，while循环仅执行一次
        TreeNode* root = t1 ? t1 : t2;
        
        queue< pair<TreeNode*,TreeNode*> > que;
        que.push(make_pair(t1,t2));
        while(!que.empty()) {
            pair<TreeNode*,TreeNode*> hp = que.front();
            que.pop();
            TreeNode* p = hp.first;
            TreeNode* q = hp.second;
            //若t1为空，循环结束；或者p非空而q空，
            //该情况出现在树t1的左或右孩子非空而树t2与之对应的孩子为空
            if(p==NULL || q==NULL) continue;
            p->val += q->val;
            //分别判断左右孩子
            if(p->left==NULL) {
                p->left = q->left;
            } else {
                que.push(make_pair(p->left,q->left));
            }
            if(p->right==NULL) {
                p->right = q->right;
            } else {
                que.push(make_pair(p->right,q->right));
            }
        }
        return root;
    }
};

637.二叉树的层平均值

/**
 * 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:
    vector<double> averageOfLevels(TreeNode* root) {
        vector<double> ans;
        queue<TreeNode*> que;
        que.push(root);
        while(!que.empty()){
            int SIZE = que.size();
            double avg = 0;
            for(int i=0;i<SIZE;i++){
                TreeNode* p = que.front();
                que.pop();
                // if(p==NULL) continue; //非空二叉树
                avg += p->val;
                if(p->left!=NULL){
                    que.push(p->left);
                }
                if(p->right!=NULL){
                    que.push(p->right);
                }
            }
            ans.push_back(avg/SIZE);
        }
        return ans;
    }
};

653.两数之和 IV - 输入 BST

最初的想法是直接返回中序遍历结果，然后问题就转化为1.两数之和。

/**
 * 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:
    void traverse(TreeNode* root, vector<int>& in){
        if(root==NULL) return ;
        traverse(root->left,in);
        in.push_back(root->val);
        traverse(root->right,in);
    }
    bool findTarget(TreeNode* root, int k) {
        vector<int> inorder;
        traverse(root,inorder);
        int SIZE = inorder.size();
        map<int,int> mp;
        bool flag = false;
        for(int i=0;i<SIZE;i++){
            if(mp.count(k - inorder[i])==1){
                flag = true;
                break;
            }
            mp.emplace(inorder[i],i);
        }
        return flag;
    }
};

/**
 * 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:
    bool findTarget(TreeNode* root, int k) {
        if(not root) return false;
        inorder(root);
        int lo = 0;
        int hi = vec.size() - 1;
        while(lo < hi){
            if(vec[lo] + vec[hi] == k) return true;
            else if(vec[lo] + vec[hi] < k) lo++;
            else hi--;
        }
        return false;
    }
private:
    vector<int> vec;
    void inorder(TreeNode* root){
        if(not root) return;
        inorder(root->left);
        vec.emplace_back(root->val);
        inorder(root->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:
    map<int, int> mp;
    bool findTarget(TreeNode* root, int k) {
        if(root==NULL){ 
              return false;
        }
        if(mp.count(k - root->val)==1){
            return true;
        }
        mp.emplace(root->val, 1);  
        return findTarget(root->right, k) || findTarget(root->left, k);
    }
};

669.修剪二叉搜索树

递归做法，设当前结点为root：

如果root->val小于L，则剪掉左子树和自身，递归处理右子树；如果root->val大于R，则剪掉右子树和自身，递归处理左子树；若root->val处在区间之间，则分别递归地处理左右子树。

/**
 * 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* trimBST(TreeNode* root, int L, int R) {
        if(root!=NULL) {
            if(root->val < L) {
                root = trimBST(root->right, L, R);
            } else if(root->val > R) {
                root = trimBST(root->left, L, R);
            } else {
                root->left = trimBST(root->left, L, R);
                root->right = trimBST(root->right, L, R);
            }
        }
        return root;
    }
};

671.二叉树中第二小的节点

最最直接的做法就是遍历一遍，使用map存储遍历结果，然后遍历一遍map寻找最小值。

上述过程也可以使用额外的一个变量记录，遍历树寻找比root（由题意，root的值一定是最小的）值大的数中最小的一个。

/**
 * 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 findSecondMinimumValue(TreeNode* root) {
        if(root==NULL || (root->left==NULL && root->right==NULL)) return -1;
        mins = root->val;
        getMin2(root);
        return ans ;
    }

    void getMin2(TreeNode* root){
        if(root!=NULL){  
            if(root->val > mins){
                if(ans==-1)
                    ans = root->val;
                else 
                    ans = min(ans,root->val);
            }
            getMin2(root->left);
            getMin2(root->right);
        }    
    }
private:
    int mins;
    int ans = -1;
};

也可以这样做：分别求左右子树的最小值，如果左右子树最小值都大于根节点的值取较小的值。其他情况取左右子树较大的值。

/**
 * 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 findSecondMinimumValue(TreeNode* root) {
        int ans = -1;
        if(root!=NULL && root->left!=NULL && root->right!=NULL) {
            // 如果当前结点的孩子的值大于当前结点的值，则无需递归遍历，
            // 因为以该孩子为根的子树最小值即为这个根
            int l = root->left->val, r = root->right->val;
            if(root->val==root->left->val){// 只有当孩子值与根相等时，才递归遍历
                l = findSecondMinimumValue(root->left);
            }
            if(root->val==root->right->val){
                r = findSecondMinimumValue(root->right);
            }
            // 问题可以转化为求左右子树的最小值
            if(l>root->val && r>root->val) {
                ans = min(l,r); // 如果左右子树最小值都大于根节点的值,取较小的值
            }else{
                ans = max(l,r); // 其他情况取左右子树较大的值
            }
        }
        return ans;
    }
};

687.最长同值路径 ★★★

思路：递归的思想，对于某个根节点root，在左子树中，与左子树根节点（root->left->val）同值的最大路径长度为L（如果root->left值与其的左右孩子值都不同，则L=0），同理，右子树记作R。

类似地，如果root的值与左孩子相同，则路径长度应当为L+1，否则左孩子到root的的路径不符合要求，记作0；右子树同理，记作R+1或0。返回左右子树中的较长路径。

函数getPath返回的是单侧的最长路径，若该路径穿越根结点，则需要加上左右两条分支路径的长度，所以在递归的过程中使用单独的变量ans记录最大路径的长度（这个长度可能是不经过根结点的单侧路径，也有可能是经过根节点的双分支路径）。

对于任意一个节点, 如果最长同值路径包含该节点, 那么只可能是两种情况：

其左右子树中加上该节点后所构成的同值路径中较长的那个继续向父节点回溯构成最长同值路径
左右子树加上该节点都在最长同值路径中, 构成了最终的最长同值路径需要注意因为要求同值, 所以在判断左右子树能构成的同值路径时要加入当前节点的值作为判断依据

/**
 * 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 longestUnivaluePath(TreeNode* root) {
        getPath(root);
        return ans;
    }

    int getPath(TreeNode* root){
        int path_len = 0;
        if(root!=NULL){
            int L = getPath(root->left); // 以左孩为根节点的最大路径长度
            int R = getPath(root->right);
            int tmp_L = 0, tmp_R = 0; // 过当前节点的路径长度，假设与孩子值不等，初始设为0
            if(root->left!=NULL && root->left->val == root->val){
                tmp_L = L + 1;
            } // 如果与左孩子值相同，path值为L+1
            if(root->right!=NULL && root->right->val == root->val){
                tmp_R += R + 1;
            } // 如果与右孩子值相同，path值为R+1
            ans = max(ans, tmp_L + tmp_R); // 递归过程中记录最大路径长度
            path_len = max(tmp_L,tmp_R);
            // 若同时和左右孩子值相同，返回较长的路径，继续向上遍历
            // 如果和左（右）孩子值不等，则路径长度设置为0
        }
        return path_len;
    }
private:
    int ans = 0;
};

700.二叉搜索树中的搜索

/**
 * 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* searchBST(TreeNode* root, int val) {
        TreeNode* ans = NULL;
        if(root!=NULL){
            if(root->val > val) {
                ans = searchBST(root->left, val);
            } else if(root->val < val) {
                ans = searchBST(root->right, val);
            } else {
                ans = root;
            }
        }
        return ans;
    }
};

783.二叉搜索树节点最小距离

/**
 * 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 minDiffInBST(TreeNode* root) {
        traverse(root);
        for(int i=0;i<nums.size()-1;i++){
            ans = min(ans, nums[i+1] - nums[i]);
        }
        return ans;
    }

    void traverse(TreeNode* root){
        if(root!=NULL){
            traverse(root->left);
            nums.push_back(root->val);
            traverse(root->right);
        }
    }
private:
    vector<int> nums;
    int ans = INT_MAX;
};

938.二叉搜索树的范围和

/**
 * 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 rangeSumBST(TreeNode* root, int L, int R) {
        int sum = 0;
        if(root!=NULL) {
            if(root->val < L) {
                sum = rangeSumBST(root->right, L, R);
            } else if(root->val > R) {
                sum = rangeSumBST(root->left, L, R);
            } else {
                sum = root->val + rangeSumBST(root->left, L, R) 
                        + rangeSumBST(root->right, L, R);
            }
        }
        return sum;
    }
};

965.单值二叉树

/**
 * 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:
    bool isUnivalTree(TreeNode* root) {
        val = root->val; //无需验空
        return dfs(root);
    }

    bool dfs(TreeNode* root){
        if(!root)return true;
        return (root->val==val) && dfs(root->left) && dfs(root->right);
        
    }
private:
    int val;
};

993.二叉树的堂兄弟节点

遍历二叉树，分别记录 x、y 结点的深度和父亲结点。

/**
 * 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 isCousins(TreeNode* root, int x, int y) {
        dfs(root, x, y, 0, nullptr);
        return (parx!=pary && dx==dy);
    }

    void dfs(TreeNode* root, int x, int y, int d,TreeNode* par) {
        if(root==NULL) return;
        if(root->val == x){
            parx = par;
            dx = d;
        }
        if(root->val == y) {
            pary = par;
            dy = d;
        }
        dfs(root->left, x, y, d+1, root);
        dfs(root->right, x, y, d+1, root);
    }
private:
    TreeNode* parx = nullptr;
    TreeNode* pary = nullptr;
    int dx=0, dy = 0;
};

1022.从根到叶的二进制数之和 ★★☆

自上而下地遍历二叉树，遇到叶子结点则表示一个"二进制"序列的值已被计算完整，加到ans上；由于自上而下不知道序列的最高位位数，所以上层的结果递归到下一级时需要×2。类似秦九韶算法。

/**
 * 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 sumRootToLeaf(TreeNode* root) {
        calculateSum(root, 0);
        return ans % M;
    }
    //由于不知道一个序列的高位位数，所以自顶向下计算数值，上一层结果×2后加上当前结点数字
    void calculateSum(TreeNode* root, int num) {
        if(root!=NULL){
            num = (num << 1) + root->val;
            if(root->left==NULL && root->right==NULL){
                ans += num; //叶子节点，当前路径计算结束，加上这个数字
            }else{//非叶子结点继续递归，对上一层的结果×2再加上当前的数字
                calculateSum(root->left, num % M);
                calculateSum(root->right, num % M);
            }    
        }
    }
private:
    int ans = 0;
    const int M = 1e9 + 7;
};

学习笔记

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议，转载请注明出处！

LeetCode专题 BFS DFS 上一篇

NumPy入门笔记下一篇

LeetCode专题 树