力扣（103、236、104）

103. 二叉树的锯齿形层序遍历

题目大意：将原先的层次遍历改为蛇形遍历，那么我们需要在102. 二叉树的层序遍历的基础上进行改进，首先蛇形走位（先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）

让我们想到设置 bool 值进行左右方向控制遍历方向，使其进入队列，但这样不如直接使用双端队列。

如果是奇数行正序进入队列，偶数行逆序进入----》奇数行元素从队头插入，偶数行从队尾插入。

/**
 * 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:
    vectorint>> ans;
    vectorint>> zigzagLevelOrder(TreeNode* root) {
        if (!root)
            return ans;
        TreeNode* visited=root;
        queue q;
        bool left = 1; // 控制左右孩子进入顺序
        q.push(visited);
        while (!q.empty()) {
            deque<int> levelList;
            int cursize = q.size();
           // ans.push_back(vector());
 
            for (int i = 0; i < cursize; i++) {
                
                q.pop();
                if (left)
                    levelList.push_back(visited->val);
                else
                    levelList.push_front(visited->val);
 
                if (visited->left) 
                    q.push(visited->left);
 
                if (visited->right) 
                    q.push(visited->right);
                visited = q.front();
                
            }
            left = !left;
            ans.emplace_back(vector<int>{levelList.begin(), levelList.end()});
        }
        return ans;
    }
};

下面来两道递归题目，树这块递归题目很多

 

104. 二叉树的最大深度 

1.确定递归函数的参数和返回值：参数就是传入树的根节点，返回就返回这棵树的深度，所以返回值为int类型。

2.确定终止条件：如果为空节点的话，就返回0，表示高度为0。

3.确定单层递归的逻辑：先求它的左子树的深度，再求右子树的深度，最后取左右深度最大的数值 再+1 （加1是因为算上当前中间节点）就是目前节点为根节点的树的深度。

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

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

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(p==root||q==root||!root)  return root;
        TreeNode *left=lowestCommonAncestor(root->left,p,q);
        TreeNode *right=lowestCommonAncestor(root->right,p,q);
        if(!left) return right;
        if(!right) return left;
        return root;
    }
};