day15 二叉树（二）

day15
代码随想录
2023.12.13

1. 102层序遍历
有关层序遍历算法还是挺简单的，也很好理解，深度遍历用的栈，而层序遍历用的队列先进先出的性质满足层序一层一层遍历的思路。所有做题思路很简单，就是一个队列先进根节点，如果队列不为空，意味着遍历未停止，然后记录对头结点的值，再将对头结点的左右子树入队，一直循环即可，最后得到层序遍历结果。
不过leetcode这道题我个人认为有的的地方是，他最终返回的结果不是简单的一维层序遍历结果，而是一个二维结果，还将层数信息表达进去了第一层的结果、第二层次的结果等等。这无疑给题目增加了一些难度，但也很好处理，主要是判断一层有几个节点，其实就是队列处理时的长度，因此代码逻辑是：首先肯定整体一个while循环，表示整理遍历；接下来就是怎么讲每一层值单独保存，在第一次while时，队列只有一个根节点，因此结果第一行只有一个值；第二次循环，队列有两个（满二叉树，好理解，缺枝的情况一样）元素，代表了第二层有两个节点，。。同理，3while时有四个元素代表了四个节点。注意这里说的都是while准备开始执行时的，执行过程中队列元素会变化！因为会不断入队出队元素，因此只需要记录while时队列的长度，然后一个for遍历队列到该size，此时就是这一层的值，这一层单独记录在一个vector，while后加入到总result中。即可！

/**
 * 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:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> result;
        queue<TreeNode*> que;
        if(root!=NULL)
            que.push(root);
        while(!que.empty()){
            int size = que.size(); //代表某一层有多少节点
            vector<int> vec;
            for(int i=0;i<size;i++){
                TreeNode*node = que.front();
                que.pop();
                vec.push_back(node->val);  //记录一层的所有值
                if(node->left)
                    que.push(node->left);
                if(node->right)
                    que.push(node->right);
            }
            result.push_back(vec); //记录所有层，一层为一行
        }
        return result;
    }
};

后面几道层序遍历扩展题就大致说一下思路即可，整理框架都是基于上述层序遍历代码的

107 层序遍历Ⅱ
这道题就是反着遍历一下，自底向上。所以就是最终result反转一下呗

/**
 * 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:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        queue<TreeNode*> que;
        if (root != NULL) que.push(root);
        vector<vector<int>> result;
        while (!que.empty()) {
            int size = que.size();
            vector<int> vec;
            for (int i = 0; i < size; i++) {
                TreeNode* node = que.front();
                que.pop();
                vec.push_back(node->val);
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
            }
            result.push_back(vec);
        }
        reverse(result.begin(), result.end()); // 在这里反转一下数组即可
        return result;
    }
};

199.二叉树的右视图
这道题就是保存每一层最后一个节点，在for中加个条件，只要是最后一个值，就保存，即可！

/**
 * 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:
    vector<int> rightSideView(TreeNode* root) {
        queue<TreeNode*> que;
        if (root != NULL) que.push(root);
        vector<int> result;
        while (!que.empty()) {
            int size = que.size();
            for (int i = 0; i < size; i++) {
                TreeNode* node = que.front();
                que.pop();
                if(i==size-1)
                    result.push_back(node->val);
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
            }
    
        }
        return result;
    }
};

637. 二叉树层均值
这道题也是for中处理不同，用一个变量记录层和，在加入到result时除以size即可。

/**
 * 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:
    vector<double> averageOfLevels(TreeNode* root) {
        queue<TreeNode*> que;
        if (root != NULL) que.push(root);
        vector<double> result;
        while (!que.empty()) {
            int size = que.size();
            double sum=0;
            for (int i = 0; i < size; i++) {
                TreeNode* node = que.front();
                que.pop();
                sum += node->val;
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
            }
            result.push_back(sum/size);
    
        }
        return result;
    }
};

429. N叉树的层序遍历
这道题只是在入队时操作不同罢了，只是之前不知道数还有node->children这个数组表示孩子的这种用法，长见识了。害，原来开始Node定义已经说明了。。。

/*
// 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<vector<int>> levelOrder(Node* root) {
        vector<vector<int>> result;
        queue<Node*> que;
        if(root!=NULL) que.push(root);
        while(!que.empty()){
            int size = que.size(); //代表某一层有多少节点
            vector<int> vec;
            for(int i=0;i<size;i++){
                Node*node = que.front();
                que.pop();
                vec.push_back(node->val);  //记录一层的所有值
                for(int j=0;j<node->children.size();j++)
                    if(node->children[j])
                        que.push(node->children[j]);
            }
            result.push_back(vec); //记录所有层，一层为一行
        }
        return result;
    }
};

515. 每个数行中找最大值
只需要在每行值时作比较，记录最大值，最后将最大值添加即可！

/**
 * 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:
    vector<int> largestValues(TreeNode* root) {
        vector<int> result;
        queue<TreeNode*> que;
        if(root!=NULL) que.push(root);
        while(!que.empty()){
            int size = que.size(); 
            vector<int> vec;
            int max=INT_MIN;
            for(int i=0;i<size;i++){
                TreeNode*node = que.front();
                que.pop();
                if(node->val>max)
                    max=node->val;
                if(node->left) que.push(node->left);
                if(node->right) que.push(node->right);
            }
            result.push_back(max); 
        }
        return result;
    }
};

116. 填充每个节点的下一个右侧节点指针
这道题，题目看了半天，才明白啥意思，就是对于一个完全二叉树，每个节点多一个next指针指向右侧节点，如果没有右侧节点，则指向NULL；剖析一下，只有每一层最右侧节点没有右侧节点，因此next指向NULL；其余节点都指向自己的右侧节点，所以for中将i与size进行判断即可。下一个问题，怎么找右侧节点？要知道，我们每次记录节点值时，都是先赋给node，在弹出。再保存node的值。代表每次保存值时，该节点已经不再队列里了。那此时队头元素是谁呢？是for中下一个要处理节点，这里是层序遍历，不就是node的右侧节点嘛！！！所以只需要将node->next指向队头即可！代码随想录这里的逻辑挺多的。。。个人感觉没必要，一行代码搞定！
这里因为所有next默认指向NULL，因此只需要处理所有有右侧节点的节点。

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;

    Node() : val(0), left(NULL), right(NULL), next(NULL) {}

    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

    Node(int _val, Node* _left, Node* _right, Node* _next)
        : val(_val), left(_left), right(_right), next(_next) {}
};
*/

class Solution {
public:
    Node* connect(Node* root) {
        queue<Node*> que;
        if(root!=NULL) que.push(root);
        while(!que.empty()){
            int size = que.size(); //代表某一层有多少节点
            vector<int> vec;
            for(int i=0;i<size;i++){
                Node*node = que.front();
                que.pop();
                if(i!=size-1)
                    node->next=que.front();
                vec.push_back(node->val);  //记录一层的所有值
                if(node->left) que.push(node->left);
                if(node->right) que.push(node->right);
            }
        }
        return root;
    }
};

117. 填充每个节点的下一个右侧节点指针Ⅱ
emm跟上一题没啥区别，只是不在是完全二叉树了，但处理逻辑一样啊，代码完全相同，就不重复了。。

104. 二叉树的最大深度
这题更简单啦，深度不就while的次数嘛，加一个变量即可，每次while中++，最后返回该值即可！

/**
 * 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 maxDepth(TreeNode* root) {
        int result = 0;
        queue<TreeNode*> que;
        if(root!=NULL)
            que.push(root);
        while(!que.empty()){
            result++;
            int size = que.size(); //代表某一层有多少节点
         
            for(int i=0;i<size;i++){
                TreeNode*node = que.front();
                que.pop();

                if(node->left)
                    que.push(node->left);
                if(node->right)
                    que.push(node->right);
            }
            
        }
        return result;
    }
};

111. 二叉树的最小深度
这道题看似有点难度，实际也很简单，要理解什么时候是最小深度。最早一次出现，左右节点都为空时！，也很好理解，这里是层序遍历，最早为空就是越靠上，也就是最小深度了嘛！！因此再左右节点判断时加一个if，若都为空直接返回resulr即可！

/**
 * 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 minDepth(TreeNode* root) {
        int result = 0;
        queue<TreeNode*> que;
        if(root!=NULL)
            que.push(root);
        while(!que.empty()){
            result++;
            int size = que.size(); //代表某一层有多少节点
         
            for(int i=0;i<size;i++){
                TreeNode*node = que.front();
                que.pop();

                if(node->left)
                    que.push(node->left);
                if(node->right)
                    que.push(node->right);
                if(node->left==NULL && node->right==NULL){
                    return result;
                }
            }
            
        }
        return result;
    }
};

到这里有关层序遍历的扩展就结束啦！我的感受就是，只要掌握层序遍历的底层逻辑，扩展都很简单！

2. 226反转二叉树
这道题很典型的递归啊，只是开始我在纠结，三行代码的顺序怎么写，但想来想去，好像没关系的样子，也测试了不同顺序，也确实没影响。。

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

当然，再深度遍历是说过，递归本质是栈实现的，因此迭代也能做，不过迭代对左右顺序就有要求啦！不能改变

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (root == NULL) return root;
        stack<TreeNode*> st;
        st.push(root);
        while(!st.empty()) {
            TreeNode* node = st.top();              // 中
            st.pop();
            swap(node->left, node->right);
            if(node->right) st.push(node->right);   // 右
            if(node->left) st.push(node->left);     // 左
        }
        return root;
    }
};

3. 对称二叉树
这道题是我感觉今天所有题最有趣的一个了，递归真的很妙！

/**
 * 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 compare(TreeNode* left, TreeNode* right) {
        // 首先排除空节点的情况
        if (left == NULL && right != NULL) return false;
        else if (left != NULL && right == NULL) return false;
        else if (left == NULL && right == NULL) return true;
        // 排除了空节点，再排除数值不相同的情况
        else if (left->val != right->val) return false;

        // 此时就是：左右节点都不为空，且数值相同的情况
        // 此时才做递归，做下一层的判断
        bool outside = compare(left->left, right->right);   // 左子树：左、 右子树：右
        bool inside = compare(left->right, right->left);    // 左子树：右、 右子树：左
        bool isSame = outside && inside;                    // 左子树：中、 右子树：中 （逻辑处理）
        return isSame;

    }
    bool isSymmetric(TreeNode* root) {
        if (root == NULL) return true;
        return compare(root->left, root->right);
    }
};