【Day 18 】2024-04-25 - 987. 二叉树的垂序遍历

[azl397985856]

987. 二叉树的垂序遍历

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/vertical-order-traversal-of-a-binary-tree

前置知识

• DFS
• 排序

  题目描述

  
  给定二叉树，按垂序遍历返回其结点值。

对位于 (X, Y) 的每个结点而言，其左右子结点分别位于 (X-1, Y-1) 和 (X+1, Y-1)。

把一条垂线从 X = -infinity 移动到 X = +infinity ，每当该垂线与结点接触时，我们按从上到下的顺序报告结点的值（Y 坐标递减）。

如果两个结点位置相同，则首先报告的结点值较小。

按 X 坐标顺序返回非空报告的列表。每个报告都有一个结点值列表。

示例 1：

输入：[3,9,20,null,null,15,7] 输出：[[9],[3,15],[20],[7]] 解释： 在不丧失其普遍性的情况下，我们可以假设根结点位于 (0, 0)： 然后，值为 9 的结点出现在 (-1, -1)； 值为 3 和 15 的两个结点分别出现在 (0, 0) 和 (0, -2)； 值为 20 的结点出现在 (1, -1)； 值为 7 的结点出现在 (2, -2)。 示例 2：

输入：[1,2,3,4,5,6,7] 输出：[[4],[2],[1,5,6],[3],[7]] 解释： 根据给定的方案，值为 5 和 6 的两个结点出现在同一位置。 然而，在报告 "[1,5,6]" 中，结点值 5 排在前面，因为 5 小于 6。

提示：

树的结点数介于 1 和 1000 之间。 每个结点值介于 0 和 1000 之间。

[zhiyuanpeng]

from collections import defaultdict
class Solution:
    def verticalTraversal(self, root: Optional[TreeNode]) -> List[List[int]]:
        nodes = []
        self.dfs(root, 0, 0, nodes)
        nodes = sorted(nodes)
        ans = defaultdict(list)
        for n in nodes:
            ans[n[0]].append(n[-1])
        return list(ans.values())

    def dfs(self, root, col, row, nodes):
        if not root:
            return
        nodes.append((col, row, root.val))
        self.dfs(root.left, col-1, row+1, nodes)
        self.dfs(root.right, col+1, row+1, nodes

Time O(nlogn) Space O(n)

[Lizhao-Liu]

class Solution {
    func verticalTraversal(_ root: TreeNode?) -> [[Int]] {
    var resultArr = [[Int]]()
    var dict = [Int: Array<Dictionary<Int, Int>>]()
    dfs(node:root, row:0, col:0, map:&dict)

    for xkey in dict.keys.sorted() {
        let arr = dict[xkey]!
        var yArr = [Int]()
        let sortedArr = arr.sorted { (dict1, dict2) -> Bool in
            let key1 = dict1.keys.first!
            let key2 = dict2.keys.first!
            if key1 > key2 {
                return true
            }else if key1 == key2 {
                return dict1[key1]! < dict2[key2]!
            }
            return false
        }
        for yDict in sortedArr {
            for (_,value) in yDict {
                yArr.append(value)
            }
        }
        resultArr.append(yArr)
    }
    return resultArr

    }

    func dfs(node:TreeNode?, row:Int, col:Int, map:inout [Int: Array<Dictionary<Int, Int>>]) {
        guard let node = node else {
            return;
        }
        map[col, default: []].append([row:node.val])
        dfs(node:node.left, row: row-1, col: col-1, map: &map)
        dfs(node:node.right, row: row-1, col: col+1, map: &map)
    }
}

[lxy1108]

思路

层次遍历树的同时记录每个节点的行和列，遍历的同时维护以列和行为键值的哈希表 根据哈希表的内容输出垂序遍历结果

python3代码

class Solution:
    def verticalTraversal(self, root: Optional[TreeNode]) -> List[List[int]]:
        queue = [(root,0,0)]
        pos_map = {}
        while queue:
            queue_tmp = []
            cur_map = {}
            for node, row, col in queue:
                if col not in cur_map.keys():
                    cur_map[col] = []
                cur_map[col].append(node.val)
                if node.left:
                    queue_tmp.append((node.left,row+1,col-1))
                if node.right:
                    queue_tmp.append((node.right,row+1,col+1))
            for k,v in cur_map.items():
                if k not in pos_map.keys():
                    pos_map[k] = {}
                pos_map[k][row] = sorted(v)
            queue = queue_tmp
        # print(pos_map)
        pos_map_keys = sorted(pos_map)
        rs = []
        for k1 in pos_map_keys:
            v1 = pos_map[k1]
            v1_keys = sorted(v1)
            cur_rs = []
            for k2 in v1_keys:
                cur_rs += v1[k2]
            rs.append(cur_rs)
        return rs

复杂度分析

时间复杂度为o(n) 因为需要对节点进行遍历

空间复杂度为o(n) 因为遍历时维护了哈希表和队列来存储节点

[wwz223]

/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var verticalTraversal = function (root) {
    let arr1 = []
    let arr2 = []
    let order = (node, deep) => {
        if (!node || node.val === null) return
        let newArr = []
        let arr1c = arr1[deep]
        let arr2c = arr2[Math.abs(deep) - 1]
        if (deep >= 0) {
            if (!arr1[deep]) {
                arr1[deep] = [node.val]
                arr1c = arr1[deep]
            } else {
                if (arr1c[arr1c.length - 1] <= node.val) {
                    newArr = arr1[deep]
                    newArr.push(node.val)
                } else {
                    arr1c.map((i) => {
                        if (node.val < i) {
                            newArr.push(node.val)
                        }
                        newArr.push(i)
                    })
                }
                arr1c = newArr
            }
            arr1[deep] = arr1c
        } else {
            if (!arr2[Math.abs(deep) - 1]) {
                arr2[Math.abs(deep) - 1] = [node.val]
                arr2c = arr2[Math.abs(deep) - 1]
            } else {

                if (arr2c[arr2c.length - 1] <= node.val) {
                    newArr = arr2[deep]
                    newArr.push(node.val)
                } else {
                    arr2c.map((i) => {
                        if (node.val < i) {
                            newArr.push(node.val)
                        }
                        newArr.push(i)
                    })
                }
                arr2c = newArr
            }
            arr2[Math.abs(deep) - 1] = arr2c
        }
        node.left && order(node.left, deep - 1)
        node.right && order(node.right, deep + 1)
    }
    order(root, 0)
    return [...arr2.reverse(), ...arr1]
};

[luzhaofeng]

class Solution:
    def verticalTraversal(self, root: TreeNode) -> List[List[int]]:
        # dfs遍历, 得到col,row,value三元组
        arr = []
        def dfs(root, row, col):
            if not root:
                return
            arr.append([col, row, root.val])
            dfs(root.left, row+1, col-1)
            dfs(root.right, row+1, col+1)
        dfs(root, 0, 0)

        # col 为第一关键字升序,row为第二关键字升序,value 为第三关键字升序
        arr = sorted(arr, key=lambda x: (x[0], x[1], x[2]), reverse=False)

        hash_ = defaultdict(list)
        for i in arr:
            hash_[i[0]].append(i[2])

        res = []
        for i in hash_.values():
            res.append(i)

        return res   

[Yukibei]

class Solution { public: vector<vector> verticalTraversal(TreeNode root) { vector<tuple<int, int, int>> data; function<void(TreeNode, int, int)> dfs = [&](TreeNode *node, int row, int col) { if (node == nullptr) { return; } data.emplace_back(col, row, node->val); dfs(node->left, row + 1, col - 1); dfs(node->right, row + 1, col + 1); }; dfs(root, 0, 0);

    vector<vector<int>> ans;
    ranges::sort(data);
    int last_col = INT_MIN;
    for (auto &[col, _, val]: data) {
        if (col != last_col) {
            last_col = col;
            ans.push_back({});
        }
        ans.back().push_back(val);
    }
    return ans;
}

};

。 时间复杂度：O(nlogn)，其中 nnn 为二叉树的节点个数。瓶颈在排序上。 空间复杂度：O(n)。

[CathyShang]

• DFS遍历树，对每个节点整理（row，col）序号，以col为key将（row，root->val）存入unordered_map哈希表，并记录min_col;
• 根据min_col向上累加遍历哈希表，对有多个value的进行排序，将值存入temp容器
• 对每一个col 汇总 res，输出答案

class Solution {
public:
    unordered_map<int, vector<pair<int, int>>> groups;
    int min_col=0;

    void dfs_987(TreeNode* root, int r, int c){
        if(root == nullptr) 
        return;
        min_col = min(min_col, c);
        groups[c].emplace_back(r,root->val);
        dfs_987(root->left, r+1, c-1);
        dfs_987(root->right, r+1, c+1);
    }
    vector<vector<int>> verticalTraversal(TreeNode* root){
        dfs_987(root,0,0);
        vector<vector<int>> res;
        cout << min_col << endl;
        int n = groups.size();
        for(int i = min_col; i < min_col + n ;i++){
            auto &g = groups[i];
            sort(g.begin(), g.end()); // 排序
            vector<int> temp;

            for(int j=0; j < g.size(); j++){
                // cout << g[j].second << endl;
                temp.push_back(g[j].second);
            }
            res.push_back(temp);
        }
        return res;
    }

};

Time: $O(nlogn)$ Space: $O(n)$

[xil324]

/**

• @param {TreeNode} root

• @return {number[][]} / var verticalOrder = function(root) { if(!root) return []; const nodeList = {}; let min = Infinity let max = Infinity (-1) const queue = []; queue.push([root, 0]); while(queue.length) { const [current, index] = queue.shift(); min = Math.min(index, min); max = Math.max(index,max);

  if(!nodeList[index]) {
      nodeList[index] = []; 
  }
  nodeList[index].push(current.val)
  if (current.left) {
      queue.push([current.left, index-1]);
  }
  if(current.right) {
     queue.push([current.right, index+1]);
  }

  }

  const result = []; for (let i = min; i < max+ 1; i++) { result.push(nodeList[i]) } return result

};

[Dtjk]

class Solution {
public:

    vector<vector<int>> verticalTraversal(TreeNode* root) {
        vector<tuple<int, int, int>> nodes;
        dfs(root, nodes, 0, 0);
        sort(nodes.begin(), nodes.end());
        vector<vector<int>> res;
        int last_col = 2000;
        for(const auto& [col, row, val]: nodes){
            if(last_col != col){
                last_col = col;
                res.emplace_back();
            }
            res.back().emplace_back(val);
        }
        return res;
    }

    void dfs(TreeNode* root, vector<tuple<int, int, int>>& nodes, int row, int col){
        if(!root) return;
        nodes.push_back(make_tuple(col, row, root->val));
        dfs(root->left, nodes, row+1, col-1);
        dfs(root->right, nodes, row+1, col+1);
    }

};

[GReyQT]

/**

• 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 { private: vector<tuple<int, int, int>> nodes;

public: vector<vector> verticalTraversal(TreeNode* root) { depth(root,0,0); sort(nodes.begin(), nodes.end());

    vector<vector<int>> res;
    int lastcol = get<0>(nodes[0]);

    for(auto it = nodes.begin(); it != nodes.end(); ++it)
    {
        if(get<0>(*it) == lastcol)
        {
            res.back().push_back(get<2>(*it));
        }
        else
        {
            lastcol = get<0>(*it);
        }
    }

    return res;
}

void depth(TreeNode* root, int row, int col) {
    // 递归的终止条件：当节点为空时
    if (root == NULL) 
    {
        return;
    } 
    else 
    {
        nodes.emplace_back(col, row, root->val);

        depth(root->left, row + 1, col - 1);
        depth(root->right, row + 1, col + 1);
    }
}

};

[YANGLimbo]

我写得好麻烦。。

class Solution {
public:
    vector<pair<pair<int,int>,int >> nodes;
public:
    void traverse(TreeNode* root, int x, int y){
        nodes.push_back({{x,y},root->val});
        if(root->left != nullptr){
            traverse(root->left, x-1,y+1);
        }
        if(root->right != nullptr){
            traverse(root->right, x+1,y+1);
        }
        return;
    }
    vector<vector<int>> verticalTraversal(TreeNode* root) {
        // 思路：先traverse并记录坐标，再根据坐标排序。不过我的横纵坐标不是题目描述里的，
        // 我是先x再y，x为横坐标y为纵坐标，从左到右从上到下从小到大
        traverse(root, 0,0);

        map<int, vector<pair<int,int>>> columns; // (x, (y,val))
        for(auto& node: nodes){
            auto& col = node.first.first; // x值
            if(columns.find(col)!=columns.end()){
                columns.at(col).push_back({node.first.second, node.second});
            }else{
                columns[col] = {{node.first.second, node.second}};
            }
        }
        for(auto& column: columns){
            auto& v = column.second;
            sort(v.begin(),v.end(),[](const pair<int,int>& a, const pair<int,int>& b){
                return a.first < b.first? true : (a.first == b.first ?(a.second < b.second) :false);
            });
        }
        vector<vector<int>> result;
        for(auto& column: columns){
            auto pairs = column.second;
            vector<int> temp(pairs.size());
            transform(pairs.begin(),pairs.end(),temp.begin(),[](const pair<int,int>& a)
            {
                return a.second;
            });
            result.push_back(temp);
        }

        return result;
    }
};