More content：力扣题记之二叉树

链式存储的二叉树节点定义方式：

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

• 二叉树递归求深度用前序，求高度用后序
• C++中map、set、multimap，multiset的底层实现都是平衡二叉搜索树，所以map、set的增删操作时间时间复杂度是logn，而unordered_map、unordered_set，底层实现是哈希表
• 257.二叉树的所有路径 + 112. 路径总和 = 113. 路径总和ii（跟着走一遍，彻底搞懂递归和回溯）

94. 二叉树的中序遍历✅

递归

class Solution {
public:
    void traversal(TreeNode *node, vector<int> &v) {
        if(!node) return ;

        traversal(node->left, v);
        v.push_back(node->val);
        traversal(node->right, v);
    }
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> v;
        traversal(root, v);
        
        return v;
    }
};

---

104. 二叉树的最大深度✅

Solution1：递归遍历，使用前序求的是深度，使用后序求的是高度

• 二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数或者节点数（取决于深度从0开始还是从1开始）
• 二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数或者节点数（取决于高度从0开始还是从1开始）

本题求最大深度，根节点的高度就是二叉树的最大深度，因此既可以使用前序遍历 ，也可以使用后序遍历

Solution2：层序遍历

class Solution1 {
public:
    int traversal(TreeNode *cur) {
        if(!cur) return 0;

        int l = traversal(cur->left);
        int r = traversal(cur->right);
        return max(l, r) + 1;
    }
    int maxDepth(TreeNode* root) {
        return traversal(root);
    }
};

class Solution2 {
public:
    int maxDepth(TreeNode* root) {
        deque<TreeNode*> dq;
        int res = 0;
        if(root) dq.push_back(root);

        while(!dq.empty()) {
            int size = dq.size();
            res++;
            while(size--) {
                TreeNode* cur = dq.front();
                dq.pop_front();
                if(cur->left) dq.push_back(cur->left);
                if(cur->right) dq.push_back(cur->right);
            }
        }

        return res;
    }
};

---

226. 翻转二叉树✅

递归三步走

简单算法题不用递归没有意义 锻炼递归思维

class Solution {
public:
    void myReverse(TreeNode* cur) {
        if(!cur) return ;
        TreeNode *tmp = cur->left;
        cur->left = cur->right;
        cur->right = tmp;
        myReverse(cur->left);
        myReverse(cur->right);
    }
    TreeNode* invertTree(TreeNode* root) {
        myReverse(root);
        return root;
    }
};

---

101. 对称二叉树❌

队列模拟太麻烦了 建议递归

注意判断逻辑怎么样最简（比代码随想录简单一倍）

class Solution {
public:
    bool digui(TreeNode* left, TreeNode* right) {
        //左右节点都为空 对称
        if(!left && !right) return true;
        //左右节点只有一个为空 或者val不相同 不对称
        if(!left || !right || left->val != right->val) return false;

        bool f = digui(left->left, right->right) && digui(right->left, left->right);
        return f;
    }
    bool isSymmetric(TreeNode* root) {
        return digui(root->left, root->right);
    }
};

---

543. 二叉树的直径❌

后序遍历就是天然的回溯

class Solution {
private:
    int ans;
public:
    int travseral(TreeNode *cur) {
        if(!cur) return 0;
   
        int l = travseral(cur->left);
        int r = travseral(cur->right);

        ans = max(ans, l + r + 1); //维护最长直径
        
        return max(l, r) + 1; //返回最大单侧路径长度，往上传递
    }
    int diameterOfBinaryTree(TreeNode* root) {
        ans = 1;
        travseral(root);
     
        return ans - 1;
    }
};

---

102. 二叉树的层序遍历✅

STL队列

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        deque<TreeNode*> dq;
        vector<vector<int>> res;
        if(!root) return res;
        
        dq.push_back(root);
        while(!dq.empty()) {
            int size = dq.size();
            vector<int> v;
            while(size--) {
                TreeNode *cur = dq.front();
                v.push_back(cur->val);
                dq.pop_front();
                if(cur->left) dq.push_back(cur->left);
                if(cur->right) dq.push_back(cur->right);
            }
            res.push_back(v);
        }

        return res;
    }
};

---

108. 将有序数组转换为二叉搜索树❌

递归取数组中间值

class Solution {
public:
    TreeNode* travseral(vector<int> &nums, int left, int right) {
        //贯彻左闭右闭
        if(left > right) return nullptr;

        int mid = left + (right - left) / 2; //防止当left和right都是int最大值时溢出
        TreeNode *cur = new TreeNode(nums[mid]);

        cur->left = travseral(nums, left, mid-1);
        cur->right = travseral(nums, mid+1, right);

        return cur;
    }
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        TreeNode *root = travseral(nums, 0, nums.size() - 1);
        
        return root;
    }
};

---

98. 验证二叉搜索树❌✅

Solution1：中序遍历，验证遍历的元素是不是从小到大

Solution2：中序遍历取出BST的val，看是否升序

class Solution1 {  
private:
    TreeNode *pre = nullptr; //记录上一个节点  
public:
    bool isValidBST(TreeNode* cur) {
        if(!cur) return true;

        bool l = isValidBST(cur->left);

        if(pre && pre->val >= cur->val) return false;
        pre = cur;

        bool r = isValidBST(cur->right);

        return l & r;
    }
};

class Solution2 {  
private:
    vector<int> v;
    void traversal(TreeNode* cur) {
        if(!cur) return;

        traversal(cur->left); 
        v.push_back(cur->val);
        traversal(cur->right); 
    }
public:
    bool isValidBST(TreeNode* root) {
        traversal(root);
        int mmin = v[0];
        for(int i = 1; i < v.size(); i++) {
            if(v[i] <= v[i - 1]) return false;
        }
        return true;
    }
};

---

230. 二叉搜索树中第 K 小的元素✅❌

Solution1：递归取出所有元素，有额外空间开销

Solution：递归利用BST的自身性质，无额外空间开销

class Solution1 {
public:
    void travseral(TreeNode *cur, vector<int> &v) {
        if(!cur) return ;
        travseral(cur->left, v);
        v.push_back(cur->val);
        travseral(cur->right, v);
        return ;
    }
    int kthSmallest(TreeNode* root, int k) {
        vector<int> v;
        travseral(root, v);

        return v[k-1];
    }
};

class Solution2 {
private:
    int res = 0;
public:
    void travseral(TreeNode *cur, int &k) { 
        //注意不要忘了& 否则子递归修改的k不会影响父递归
        if(!cur) return ;
        travseral(cur->left, k);
        k--;
        if(k == 0) {
            res = cur->val;
            return ;
        }
        travseral(cur->right, k);
    }
    int kthSmallest(TreeNode* root, int k) {
        travseral(root, k);

        return res;
    }
};

---

199. 二叉树的右视图✅

简单

class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        vector<int> res;
        deque<TreeNode*> dq;
        
        if(root) dq.push_back(root);
        while(!dq.empty()) {
            int size = dq.size();
            for(int i = 0; i < size; i++) {
                TreeNode *cur = dq.front();
                if(size - 1 == i) res.push_back(cur->val);
                dq.pop_front();
                if(cur->left) dq.push_back(cur->left);
                if(cur->right) dq.push_back(cur->right);
            }
        }

        return res;
    }
};

---

114. 二叉树展开为链表❌

钻牛角尖了，如果想遍历和展开同步，就不要递归

直接用最暴力的方法吧 把节点都存起来

class Solution {
public:
    void travseral(TreeNode* cur, vector<TreeNode*> &v) {
        if(!cur) return ;

        v.push_back(cur);
        travseral(cur->left, v);
        travseral(cur->right, v);
    }
    void flatten(TreeNode* root) {
        vector<TreeNode*> v;
        travseral(root, v);

        TreeNode *dummy = new TreeNode(0);
        TreeNode *pre = dummy;
        for(const auto &i : v) {
            pre->left = nullptr;
            pre->right = i;
            pre = pre->right;
        }
         
        root = dummy->right;
    }
};

---

105. 从前序与中序遍历序列构造二叉树✅

同106. 从中序与后序遍历序列构造二叉树

link：力扣题记之二叉树

class Solution {
public:
    TreeNode* travseral(vector<int>& preorder, int preorderBegin, int preorderEnd, vector<int>& inorder, int inorderBegin, int inorderEnd) {
        if(inorderEnd == inorderBegin) return nullptr;

        int root_val = preorder[preorderBegin];
        TreeNode *root = new TreeNode(root_val);
        if(inorderEnd == inorderBegin + 1) return root;
        
        int cutIndex = 0;
        for(cutIndex = inorderBegin; cutIndex < inorderEnd; cutIndex++) {
            if(inorder[cutIndex] == root_val) break;
        }

        int leftInorderBegin = inorderBegin;
        int leftInorderEnd = cutIndex;
        int rightInorderBegin = cutIndex + 1;
        int rightInorderEnd = inorderEnd;

        int leftPreorderBegin = preorderBegin + 1;
        int leftPreorderEnd = preorderBegin + leftInorderEnd - leftInorderBegin;
        int rightPreorderBegin = preorderBegin + leftInorderEnd - leftInorderBegin + 1;
        int rightPreorderEnd = preorderEnd;

        root->left = travseral(preorder, leftPreorderBegin, leftPreorderEnd, inorder, leftInorderBegin, leftInorderEnd);
        root->right = travseral(preorder, rightPreorderBegin, rightPreorderEnd, inorder, rightInorderBegin, rightInorderEnd);

        return root;
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        return travseral(preorder, 0, preorder.size(), inorder, 0, inorder.size());
    }
};

---

※437. 路径总和 III✅

路径问题集大成者

Solution1：理清思路 注释很详细

Solution2：上面的写法参考了112. 路径总和，后来一思考发现把寻找函数写成bool类型的完全没必要啊，还搞得特别复杂，如果想要更简洁就把主函数和遍历函数写在一起，再把res变量写成全局变量，就不用在每个函数里都加上它的引用参数了（可以但没必要，现在的结构思路比较清晰）

class Solution1 {
public:
    bool findPath(TreeNode *cur, long long int sum, int &res) {
        //即使搜到了路径也不要直接返回 继续往下搜 因为可能有包含情况
        //比如【1，-2】和【1，-2，1，-1】都满足题意
        if(!sum) res++; 
        // if(!sum) return true;
        

        if(!cur->left && !cur->right) return false;

        if(cur->left) {
            sum -= cur->left->val;
            //搜到也不应该像路径总和1那样直接返回了
            //因为那是搜出一条来就行 这里是要搜出所有路径
            //以某一个节点为起点的路径可能有多条
            if(findPath(cur->left, sum, res)) {
                //因为在调用过程中搜到也不会返回true 因此这里必定返回false
            }
            sum += cur->left->val;
        }
        if(cur->right) {
            sum -= cur->right->val;
            if(findPath(cur->right, sum, res)) {
                //因为在调用过程中搜到也不会返回true 因此这里必定返回false
            }
            sum += cur->right->val;
        }
        
        return false;
    }
    void travseral(TreeNode *cur, long long int targetSum, int &res) {
        if(!cur) return ;
        //以每个节点都当成起始点搜一遍
        //此判断只针对cur节点自己就构成一条路径的情况
        //正常情况下res增加是在17行完成的 因为调用findPath函数只要不是46行
        //的情况就都最终返回41行false 因此在50行不会res++ 所以不用担心res重复++
        if(findPath(cur, targetSum - cur->val, res)) {
            res++;
            // cout << cur->val << endl;
        }
        
        travseral(cur->left, targetSum, res);
        travseral(cur->right, targetSum, res);
    }
    int pathSum(TreeNode* root, int targetSum) {
        int res = 0;
        if(!root) return 0;
        targetSum =  (long long int)targetSum; //不然处理大负数时会报错
        travseral(root, targetSum, res);

        return res;
    }
};

class Solution2 {
public:
    void findPath(TreeNode *cur, long int sum, int &res) {
        //即使搜到了路径也不要直接返回 继续往下搜 因为可能有包含情况
        //比如【1，-2】和【1，-2，1，-1】都满足题意
        if(!sum) res++;         

        if(!cur->left && !cur->right) return ; //到叶子节点了就终止

        if(cur->left) {
            sum -= cur->left->val;
            findPath(cur->left, sum, res);       
            sum += cur->left->val; //回溯
        }
        if(cur->right) {
            sum -= cur->right->val;
            findPath(cur->right, sum, res);            
            sum += cur->right->val;
        }
        
        return ;
    }
    void travseral(TreeNode *cur, long int targetSum, int &res) {
        if(!cur) return ;

        findPath(cur, targetSum - cur->val, res);
        
        travseral(cur->left, targetSum, res);
        travseral(cur->right, targetSum, res);
    }
    int pathSum(TreeNode* root, int targetSum) {
        int res = 0;
        if(!root) return 0;
        targetSum =  (long int)targetSum; //不然处理大负数时会报错
        travseral(root, targetSum, res);

        return res;
    }
};

---

236. 二叉树的最近公共祖先❌

从目标节点开始自底向上回溯（只能后序）一层层传过去

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(!root || root == p || root == q) return root;
        //找某一条路径就要在递归中及时return，而遍历整棵树就像下面这样用
        //节点来承接，递归完统一处理左右两个递归，即处理后序遍历的中间节点
        //遍历整个树不代表要把每个点都处理 比如示例一搜了三个点就返回了
        //但如果p q都是叶子节点 那就要搜完整棵树了 比如代码随想录的示例图
        TreeNode *left = lowestCommonAncestor(root->left, p, q); //左
        TreeNode *right = lowestCommonAncestor(root->right, p, q); //右
        //中:
        //这里return的就是左右两棵子树各一个p q 当下的root就是最近公共祖先
        if(left && right) return root; 
        //这里return的就是左右两棵子树最多有一棵搜到了p和q 继续往上传递直到根节点  
        if(!left && right) return right;
        else if(left  && !right) return left;
        else return nullptr;
    }
};

---

※124. 二叉树中的最大路径和❌

类似543. 二叉树的直径

class Solution {
private:
    int sum;  
public:
    int travseral(TreeNode* cur) {
        if(!cur) return 0;

        int l = max(0, travseral(cur->left)); //如果为负值就视为0，不走该路径  
        int r = max(0, travseral(cur->right));  
        sum = max(sum, l + r + cur->val); //维护最大路径和  

        return max(l, r) + cur->val; //返回最大单侧路径和 
    }
    int maxPathSum(TreeNode* root) {
        sum = root->val;
        travseral(root);

        return sum;
    }
};