力扣--树题总结

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

/**
 * 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:
    int minDiffInBST(TreeNode* root) {
        int ans = INT_MAX, pre = -1;
        dfs(root, pre, ans);
        return ans;
    }

    void dfs(TreeNode* root, int& pre, int& ans){
        //递归返回条件
        if(root == nullptr){
            return;
        }
        //前-一直递归到左下角
        dfs(root->left, pre, ans);
        //中-处理数据，第一次pre保存左下角值
        if(pre == -1){
            pre = root->val;
        }else{
            //递归退回到左下角父节点，ans取最小
            ans = min(ans, root->val - pre);
            //pre更新到当前节点的val
            pre = root->val;
        }
        //后续
        dfs(root->right, pre, ans);
    }
};

872. 叶子相似的树

/**
 * 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 leafSimilar(TreeNode* root1, TreeNode* root2) {
        vector<int> num1;
        vector<int> num2;
        inorder(root1, num1);
        inorder(root2, num2);
        if(num1.size() != num2.size()) return false;
        for(int i=0; i< num1.size(); i++){
            if(num1[i] != num2[i]) return false;
        }
        return true;
    }

    void inorder(TreeNode* root, vector<int>& num){
        if(root==nullptr){
            return;
        }
        inorder(root->left, num);
        if(root->left==nullptr && root->right==nullptr){
            num.push_back(root->val);
        }
        inorder(root->right, num);
    }
};

897. 递增顺序搜索树

/**
 * 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* increasingBST(TreeNode* root) {
        vector<int> res;
        TreeNode* head = new TreeNode();
        TreeNode* p = head;
        dfs(root, res);
        for(int val: res){
            TreeNode* node = new TreeNode(val);
            p->right = node;
            p = p->right;
        }
        return head->right;
    }

    void dfs(TreeNode* root, vector<int>& res){
        if(root == nullptr){
            return;
        }
        dfs(root->left, res);
        res.push_back(root->val);
        dfs(root->right, res);
    }
};