day27

标签：node right TreeNode val day27 que left

【102 二叉树的层序遍历】

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

关于使用容器进行定义
- vector<vector<int>> result; 主函数返回结果是二维数组数据结构是vector 数据类型是int 注意写法
- queue<TreeNode*> que; 队列要存储的是结点数据结构是queue 数据类型是TreeNode* 注意写法不要写错成int 没int什么事
当队列不为空的时候取队头元素即为当前根结点出队并做输出到结果数组的操作同时把左右孩子入队--如果有的话但是注意层次遍历返回结果是二维数组每一层是一个一维数组所有层组成二维数组因此需要一层一层push_back到一个又一个一维的temp数组最后再push_back到二维result数组而什么时候就是一层遍历结束了呢------用队列长度来度量即可-----注意这里的队列长度指的是遍历完一层结点之后的前队列的长度因为后队列始终是变化的所以需要先记下前队列长度为size 再用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 {
    void eachLevel(TreeNode* root, vector<int>&temp) {
        while (root != NULL) {
            temp.push(root->val);
            temp.push(root->left->val);
            temp.push(root->righr->val);
            if (root->left) eachLevel(root->left, temp); 
            if (root-->right)   eachLevel(root->right, temp); 
        }
    }
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<int> &temp;
    }
};

不能运行感觉写着写着就成了迭代法了标准答案见下

# 递归法
class Solution {
public:
    void order(TreeNode* cur, vector<vector<int>>& result, int depth)
    {
        if (cur == nullptr) return;
        if (result.size() == depth) result.push_back(vector<int>());
        result[depth].push_back(cur->val);
        order(cur->left, result, depth + 1);
        order(cur->right, result, depth + 1);
    }
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> result;
        int depth = 0;
        order(root, result, depth);
        return result;
    }
};

我看其余几道层次遍历都用的是迭代法这个递归法不好懂先暂且搁置以后再看

【107 二叉树的层次遍历II】

我的思路是在[102]基础上反转最后数组即可但是我的反转函数调用的方式不正确了这个错误至少已经出现两次了要注意

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

reverse(result.begin(), result.end()); 记住这个反转数组的reverse函数
还有一处错误就是 TreeNode* node = que.front(); 位置放在for循环内因为每次都是当前根都是重新取值并不是一成不变的

【199 二叉树的右视图】

我的思路错误错在把右视图等价成了最右边一列的元素举个例子假设某棵树只有左子树照我原先的理解只输出最右边一列的元素的话那难道这棵树只输出根节点吗只需要遍历即入队列右孩子就行全然不管不顾左孩子了吗当然不是！既然是右视图那只要右边没有把左边元素挡住左边的元素即左孩子还是需要输出的因此正确的思路是输出该层最后一个元素值而至于遍历即入队列这个操作左右孩子都是需要执行的

/**
 * 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) {
        vector<int> result;
        queue<TreeNode*> que;
        if (root != NULL)   que.push(root);
        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;
    }
};

注意队头即当前根节点后面是要进左右孩子的而此刻这个根是注定在取到这个元素值时就是要pop出来的只是相比之前pop的同时并不是无条件就跟着输出即存储到result数组中而是满足一定条件（i == size - 1) 才执行输出即存储到result数组语句的

【637 二叉树的层平均值】

思路遍历还是一样只是不需要每次都把当前根节点->val值push到result数组而是在每层For循环结束时把所有原本要push的结点求取平均值就好

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

我原本是要用temp存储这些值等到一轮结束后给result.push_back(当前temp的均值) 但这样的话不仅求temp均值还需要额外操作每层for循环还需要temp还原成初始值
更好的思路是 temp直接随着for循环累积每层元素之和最后只需要temp/size即可获得每层元素平均值代码见上

【429 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<vector<int>> levelOrder(Node* root) {
        vector<vector<int>> result;
        queue<Node*> que;
        if (root == NULL)   que.push(root);
        while (!que.empty()) {
            vector<int> temp;
            int size = que.size();
            for (int i = 0; i <size; i++) {
                Node* node = que.front();
                que.pop();
                temp.push_back(node->val);
                for (int j = 0; j < node->children.size(); j++)
                    que.push(node->children->val);
            }
            result.push_back(temp);
        }
        return result;
    }
};

我知道区别只在于不是两孩子了变成了多个孩子了遍历语句与赋值语句不正确

/*
// 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()) {
            vector<int> temp;
            int size = que.size();
            for (int i = 0; i <size; i++) {
                Node* node = que.front();
                que.pop();
                temp.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(temp);
        }
        return result;
    }
};

看懂题目定义的 node数据结构很重要这样就理解了chidren是一个存放node类型的指针数组既然是数组那就可通过下标访问各结点
if (root != NULL) que.push(root); 这句话千万别忘了写也别写错了
- 老爱写成root==NULL return..... 注意这里是要先让根入队列而不需要返回什么值
- nullptr是针对链表结点ListNode* NULL针对树节点指针TreeNode*

【515 在每个树行中找最大值】

思路没错就是102基础之上把temp变成经比较后较大值

/**
 * 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()) {
            TreeNode* node = que.front();
            int temp = node->val;
            int size = que.size();
            for (int i = 0; i < size; i++) {
                TreeNode* node = que.front();
                que.pop();
                temp = temp > node->val ? temp : node->val;
                if (node->left)     que.push(node->left);
                if (node->right)    que.push(node->right);
            }
            result.push_back(temp);
        }
        return result;
    }
};

值得注意的是这里给temp赋初值需要注意不能是0-----因为元素值有可能都是复数不能是root->val因为这个是最原始根节点值其大小并不涉及每一层有两种方式
- 要么重复写后面的一段代码 TreeNode* node = que.front(); int temp = node->val;
- 要么调用常量int temp = INT_MIN;

标签：node,right,TreeNode,val,day27,que,left
From： https://www.cnblogs.com/deservee/p/16930577.html

相关文章

赞助商

阅读排行