[数据结构与算法]leetcode987. 二叉树的垂序遍历

#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
#include<sstream>
#include<queue>
using namespace std;

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>> verticalTraversal(TreeNode* root) {
        vector<vector<int>> mList;
        dfs(root, 0, 0, mList);
        sort(mList.begin(), mList.end(), [](vector<int> arr1, vector<int> arr2)->bool {
            //[0]->节点值，[1]->节点所在行，[2]->节点所在列
            if (arr1[2] != arr2[2]) return arr1[2] < arr2[2];//列不相同，列小放前面
            if (arr1[1] != arr2[1]) return arr1[1] < arr2[1];//列相同，行不相同，行小放前面
            return arr1[0] < arr2[0];//列相同，行相同，值小的放前面
            });
        vector<vector<int>> ans;
        // 二维(多维)vector添加一个空项
        ans.push_back({});
        for (int i = 0; i < mList.size(); i++) {
            vector<int> arr = mList[i];
            int val = arr[0];
            if (i > 0 && arr[2] != mList[i - 1][2]) {
                ans.push_back({});
            }
            ans.back().push_back(val);
        }
        return ans;
    }
    void dfs(TreeNode* root, int row, int col, vector<vector<int>>& mList) {
        if (root == NULL) return;
        mList.push_back({ root->val,row,col });
        dfs(root->left, row + 1, col - 1, mList);
        dfs(root->right, row + 1, col + 1, mList);
    }
};
//层序遍历建二叉树
TreeNode* buildTree(vector<int> a, int n)
{
    int i;
    TreeNode* root = NULL;
    TreeNode* queue[11];
    int front = 0, rear = 0;//按层，使用队列 
    for (i = 0; i < n; i++) {
        /*初始化新节点*/
        TreeNode* t;
        if (a[i] == NULL) t = NULL;
        else {
            t = (TreeNode*)malloc(sizeof(TreeNode));
            t->left = t->right = NULL;
            t->val = a[i];
        }
        /*入队*/
        queue[++rear] = t;
        if (i == 0) {
            root = t;
        }
        else {
            if (!queue[rear / 2]->left) {
                queue[rear / 2]->left = t;
            }
            else {
                queue[rear / 2]->right = t;
                front++;
            }
        }
    }
    return root;
}
int main() {
    TreeNode* root;
    vector<int> tree = {3, 9, 20, NULL, NULL, 15, 7};
    root = buildTree(tree,tree.size());
    Solution().verticalTraversal(root);
    return 0;
}

知识点：

1、层序遍历建二叉树

TreeNode* buildTree(vector<int> a, int n)
{
    int i;
    TreeNode* root = NULL;
    TreeNode* queue[11];
    int front = 0, rear = 0;//按层，使用队列 
    for (i = 0; i < n; i++) {
        /*初始化新节点*/
        TreeNode* t;
        if (a[i] == NULL) t = NULL;
        else {
            t = (TreeNode*)malloc(sizeof(TreeNode));
            t->left = t->right = NULL;
            t->val = a[i];
        }
        /*入队*/
        queue[++rear] = t;
        if (i == 0) {
            root = t;
        }
        else {
            if (!queue[rear / 2]->left) {
                queue[rear / 2]->left = t;
            }
            else {
                queue[rear / 2]->right = t;
                front++;
            }
        }
    }
    return root;
}

2、二维(多维)vector添加一个空项

vector<vector<int>> ans;
// 二维(多维)vector添加一个空项
ans.push_back({});

3、lambda表达式

sort(mList.begin(), mList.end(), [](vector<int> arr1, vector<int> arr2)->bool {
            //[0]->节点值，[1]->节点所在行，[2]->节点所在列
            if (arr1[2] != arr2[2]) return arr1[2] < arr2[2];//列不相同，列小放前面
            if (arr1[1] != arr2[1]) return arr1[1] < arr2[1];//列相同，行不相同，行小放前面
            return arr1[0] < arr2[0];//列相同，行相同，值小的放前面
            });