【Day 53 】2023-04-07 - Top-View-of-a-Tree

[azl397985856]

Top-View-of-a-Tree

入选理由

暂无

题目地址

https://binarysearch.com/problems/Top-View-of-a-Tree

前置知识

暂无

题目描述

Given a binary tree root, return the top view of the tree, sorted left-to-right.

Constraints

n ≤ 100,000 where n is the number of nodes in root

[JiangyanLiNEU]

• leetcode 987
• DFS + Heap
• T = O(LogN) N = len(Nodes)

• S = O(N) N = len(Nodes)

  class Solution:
  def verticalTraversal(self, root: Optional[TreeNode]) -> List[List[int]]:
      heap = []
      heapq.heapify(heap)
      def labelNode(tree, row, col):
          heapq.heappush(heap, [col, row, tree.val])
          if tree.left:
              labelNode(tree.left, row+1, col-1)
          if tree.right:
              labelNode(tree.right, row+1, col+1)
  
      labelNode(root, 0, 0)
      result = []
      curCol = float('-inf')
  
      while heap:
          [col, row, value] = heapq.heappop(heap)
          if col>curCol:
              curCol = col
              result.append([])
          result[-1].append(value)
      return result

[lp1506947671]

​

# class Tree:
#     def __init__(self, val, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def solve(self, root):
        q = collections.deque([(root, 0)])
        d = {}
        while q:
            cur, pos = q.popleft()
            if pos not in d:
                d[pos] = cur.val
            if cur.left:
                q.append((cur.left, pos - 1))
            if cur.right:
                q.append((cur.right, pos + 1))
        return list(map(lambda x:x[1], sorted(d.items(),key=lambda x: x[0])))

令 n 节点数

复杂度分析

• 时间复杂度：我们使用了排序，并且所有节点最多只处理一次，因此时间复杂度为 O(nlogn)
• 空间复杂度：哈希表最多容纳 n 个元素，因此空间复杂度为 O(n)

[LIMBO42]

/**
 * 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>> verticalTraversal(TreeNode* root) {
        map<int, vector<pair<int, int>>> m;
        queue<pair<TreeNode*, int>> que;
        que.push(make_pair(root, 0));
        int row = 0;
        while(!que.empty()) {
            int size = que.size();
            for(int i = 0; i < size; ++i) {
                auto it = que.front();
                que.pop();
                TreeNode* node = it.first;
                int index = it.second;
                m[index].push_back(make_pair(node->val, row));
                if(node->left) {
                    que.push(make_pair(node->left, index-1));
                }
                if(node->right) {
                    que.push(make_pair(node->right, index+1));
                }
            }
            row++;
        }
        vector<vector<int>> ans;
        for(auto &it : m) {
            auto vec = it.second;
            sort(vec.begin(), vec.end(), [&](const pair<int, int> &a, const pair<int, int> &b){
                if(a.second == b.second) {
                    return a.first < b.first;
                }
                return a.second < b.second;
            });
            // ans.push_back(vec);
            vector<int> p(vec.size());
            for(int i = 0; i < vec.size(); ++i) {
                p[i] = vec[i].first;
            }
            ans.push_back(p);
        }
        return ans;
    }
};

[bookyue]

TC: O(n)
SC: O(n)

    public List<List<Integer>> verticalTraversal(TreeNode root) {
        Map<Integer, List<int[]>> map = new TreeMap<>();
        Queue<TreeNode> queue = new ArrayDeque<>();
        Queue<Integer> queueOfCol = new ArrayDeque<>();
        queue.offer(root);
        queueOfCol.offer(0);

        int row = 0;
        while (!queue.isEmpty()) {
            for (int i = queue.size(); i > 0; i--) {
                var cur = queue.poll();
                int col = queueOfCol.poll();

                map.computeIfAbsent(col, o -> new ArrayList<>()).add(new int[]{row, cur.val});

                if (cur.left != null) {
                    queue.offer(cur.left);
                    queueOfCol.offer(col - 1);
                }

                if (cur.right != null) {
                    queue.offer(cur.right);
                    queueOfCol.offer(col + 1);
                }
            }

            row++;
        }

        List<List<Integer>> ans = new ArrayList<>();
        for (List<int[]> list : map.values()) {
            list.sort((a, b) -> a[0] != b[0] ? Integer.compare(a[0], b[0]) : Integer.compare(a[1], b[1]));
            List<Integer> cur = new ArrayList<>(list.size());
            list.forEach(v -> cur.add(v[1]));

            ans.add(cur);
        }

        return ans;
    }

[NorthSeacoder]

function solve(root) {
    const q = []; // 创建一个队列来存储当前节点以及它的位置信息
    q.push([root, 0]);
    const d = {}; // 创建一个字典来存储每个位置上的节点值
    while (q.length) {
        const [cur, pos] = q.shift();
        if (!(pos in d)) {
            d[pos] = cur.val;
        }
        if (cur.left) {
            q.push([cur.left, pos - 1]);
        }
        if (cur.right) {
            q.push([cur.right, pos + 1]);
        }
    }
    // 按照位置排序并将节点值放到数组中返回
    return Object.entries(d)
        .sort((a, b) => a[0] - b[0])
        .map((item) => item[1]);
}

• TC:O(n)
• SC:O(n)

[kofzhang]

思路

DFS ，好像刚做过？

复杂度

时间复杂度：O(nlogn) 空间复杂度：O(n)

代码

class Solution:
    def verticalTraversal(self, root: Optional[TreeNode]) -> List[List[int]]:
        d = defaultdict(list)
        def dfs(node,row,col):
            if not node:
                return 
            d[col].append((row,node.val))
            dfs(node.left,row+1,col-1)
            dfs(node.right,row+1,col+1)
            return

        dfs(root,0,0)
        ans = []

        for k,v in sorted(d.items(),key=lambda x:x[0]):
            v.sort()
            ans.append([val for _,val in v])
        return ans

[chanceyliu]

思路

二叉树的垂序遍历做过

代码

class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
    this.val = val === undefined ? 0 : val;
    this.left = left === undefined ? null : left;
    this.right = right === undefined ? null : right;
  }
}

function verticalTraversal(root: TreeNode | null): number[][] {
  const nodes = [];

  const dfs = (node, row, col, nodes) => {
    if (node === null) {
      return;
    }
    nodes.push([col, row, node.val]);
    dfs(node.left, row + 1, col - 1, nodes);
    dfs(node.right, row + 1, col + 1, nodes);
  };

  dfs(root, 0, 0, nodes);
  nodes.sort((tuple1, tuple2) => {
    if (tuple1[0] !== tuple2[0]) {
      return tuple1[0] - tuple2[0];
    } else if (tuple1[1] !== tuple2[1]) {
      return tuple1[1] - tuple2[1];
    } else {
      return tuple1[2] - tuple2[2];
    }
  });

  const ans: number[][] = [];
  let lastcol = -Number.MAX_VALUE;
  for (const tuple of nodes) {
    let col = tuple[0],
      row = tuple[1],
      value = tuple[2];
    if (col !== lastcol) {
      lastcol = col;
      ans.push([]);
    }
    ans[ans.length - 1].push(value);
  }
  return ans;
}

[zhangyu1131]

// 利用先序dfs+map
class Solution {
public:
    vector<vector<int>> verticalTraversal(TreeNode* root) {
        if (!root)
        {
            return {};
        }

        map<int, vector<NodeData>> vertical_node_map; // key是纵坐标，值是该纵坐标上的横坐标和节点值
        preOrder(root, 0, 0, vertical_node_map);

        // 排序并输出
        for (auto& pair : vertical_node_map)
        {
            if (!pair.second.empty())
            {
                std::sort(pair.second.begin(), pair.second.end(), [](NodeData& n1, NodeData& n2)
                {
                    if (n1.row < n2.row)
                    {
                        return true;
                    }
                    if (n1.row > n2.row)
                    {
                        return false;
                    }
                    return n1.val < n2.val;
                });
            }
        }

        vector<vector<int>> res;
        for (auto& pair : vertical_node_map)
        {
            if (!pair.second.empty())
            {
                vector<int> tmp;
                for (auto& node : pair.second)
                {
                    tmp.push_back(node.val);
                }
                res.push_back(std::move(tmp));
            }
        }

        return res;
    }

private:
    struct NodeData
    {
        int row;
        int val;
    };

    void preOrder(TreeNode* root, int row, int col, map<int, vector<NodeData>>& vertical_node_map)
    {
        if (!root)
        {
            return;
        }

        NodeData data{row, root->val};
        vertical_node_map[col].push_back(std::move(data));
        preOrder(root->left, row + 1, col - 1, vertical_node_map);
        preOrder(root->right, row + 1, col + 1, vertical_node_map);
    }
};

[FireHaoSky]

思路：哈希表+dfs

代码：python

class solution:
    def top_view(root):
        if not root:
            return []
        map = {}

        def dfs(node, row, col, map):
            if not node:
                return
            if col not in map:
                map[col] = [node.val, row]
            else:
                if row < map[col][1]:
                    map[col] = [node.val, row]

            dfs(node.left, row+1, col-1, map)
            dfs(node.right, row+1, col-1, map)

        dfs(root, 0,0,map)
        sorted_keys = sorted(map.key())

        return [map[key][0] for key in sorted_keys]

复杂度分析：

"""
时间复杂度：O(n)
空间复杂度：O(n)
"""

[wangqianqian202301]

class newNode:
    def __init__(self, key):
        self.data = key
        self.left = None
        self.right = None
        self.hd = 0
def topview(root):
    if(root == None):
        return
    q = []
    m = dict()
    hd = 0
    root.hd = hd
    q.append(root)
    while(len(q)):
        root = q[0]
        hd = root.hd
        if hd not in m:
            m[hd] = root.data
        if(root.left):
            root.left.hd = hd - 1
            q.append(root.left)

        if(root.right):
            root.right.hd = hd + 1
            q.append(root.right)

        q.pop(0)
    for i in sorted(m):
        print(m[i], end=" ")

[Zoeyzyzyzy]

class SolutionApr6 {
    //Method 1: HashMap + sort + DFS
    Map<TreeNode, int[]> map = new HashMap<>();

    public List<List<Integer>> verticalTraversal(TreeNode root) {
        map.put(root, new int[] { 0, 0, root.val });
        dfs(root);
        List<int[]> list = new ArrayList<>(map.values());
        Collections.sort(list, (a, b) -> {
            if (a[0] != b[0])
                return a[0] - b[0];
            if (a[1] != b[1])
                return a[1] - b[1];
            return a[2] - b[2];
        });
        List<List<Integer>> res = new ArrayList<>();
        int preCol = Integer.MIN_VALUE;
        for (int[] each : list) {
            if (each[0] != preCol) {
                preCol = each[0];
                res.add(new ArrayList<>());
            }
            res.get(res.size() - 1).add(each[2]);
        }
        return res;
    }

    private void dfs(TreeNode root) {
        if (root == null)
            return;
        int[] info = map.get(root);
        int col = info[0], row = info[1], value = info[2];
        if (root.left != null) {
            map.put(root.left, new int[] { col - 1, row + 1, root.left.val });
            dfs(root.left);
        }
        if (root.right != null) {
            map.put(root.right, new int[] { col + 1, row + 1, root.right.val });
            dfs(root.right);
        }
    }

    //Method2: BFS
    //The difference between BFS and DFS would only be the traverse process.
        //其实分为两步：1. BFS将这些组合添加进去； 2. 分组排序
        public List<List<Integer>> verticalTraversal1(TreeNode root) {
            List<int[]> tuples = BFS(root);
            Collections.sort(tuples, (a, b) -> {
                if (a[0] != b[0])
                    return a[0] - b[0];
                if(a[1] != b[1])
                    return a[1] - b[1];
                return a[2] - b[2];
            });
            List<List<Integer>> res = new ArrayList<>();
            int preCol = Integer.MIN_VALUE;
            int size = 0;
            for (int[] tuple : tuples) {
                if (tuple[0] != preCol) {
                    res.add(new ArrayList<>());
                    size++;
                    preCol = tuple[0];
                }
                res.get(size - 1).add(tuple[2]);
            }
            return res;
        }

        class Tuple {
            TreeNode node;
            int col;
            int row;

            Tuple(TreeNode node, int col, int row) {
                this.node = node;
                this.row = row;
                this.col = col;
            }
        }

        private List<int[]> BFS(TreeNode node) {
            ArrayList<int[]> res = new ArrayList<>();
            LinkedList<Tuple> queue = new LinkedList<>();
            queue.offer(new Tuple(node, 0, 0));
            Tuple cur;
            int size, row, col;

            while (!queue.isEmpty()) {
                size = queue.size();
                while (size-- > 0) {
                    cur = queue.poll();
                    col = cur.col;
                    row = cur.row;
                    res.add(new int[] { col, row, cur.node.val });
                    if (cur.node.left != null)
                        queue.add(new Tuple(cur.node.left, col - 1, row + 1));
                    if (cur.node.right != null)
                        queue.add(new Tuple(cur.node.right, col + 1, row + 1));
                }
            }
            return res;
        }

}

[harperz24]

class Solution:
    def verticalTraversal(self, root: Optional[TreeNode]) -> List[List[int]]:
        self.node_ls = []
        # construct the node list, with the coordinates
        self.dfs(root, 0, 0)
        # sort the node list globally, according to the coordinates
        y_map = collections.defaultdict(list)
        for y, x, val in sorted(self.node_ls):
            y_map[y].append(val)

        return list(y_map.values())

    def dfs(self, root, y, x):
        if not root:
            return 
        # preorder
        self.node_ls.append((y, x, root.val))
        self.dfs(root.left, y - 1, x + 1)
        self.dfs(root.right, y + 1, x + 1)

        # dfs + sort
        # time: O(nlogn)
        # space: O(n)

[aoxiangw]

from collections import deque, defaultdict

class TreeNode:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def top_view(self, root):
        if not root:
            return []
        hd = defaultdict(list)
        queue = deque([(root, 0)])
        while queue:
            cur, pos = queue.popleft()
            hd[pos].append(cur.val)
            if cur.left:
                queue.append(cur.left, pos - 1)
            if cur.right:
                queue.append(cur.right, pos + 1)

        return [hd[pos][0] for pos in sorted(hd.keys())]

time, space: O(nlogn), O(n)

[sye9286]

思路

代码

class Node
{
    constructor(data)
    {
        this.data=data;
        this.left = this.right = null;
        this.head = 0;
    }
}

function topview(root)
{
    if(root == null)
        return;
    let q = [];
    let m = new Map();
    let head = 0;
    root.head = head;
    q.push(root);

    while(q.length!=0)
    {
        root = q[0];
        head = root.head;
        if(!m.has(head))
            m.set(head,root.data);
        if(root.left)
        {
            root.left.head = head - 1;
            q.push(root.left);
        }
        if(root.right)
        {
            root.right.head = head + 1;
            q.push(root.right);
        }
        q.shift()
    }

    let arr = Array.from(m);
    arr.sort(function(a,b){return a[0]-b[0];})

    for (let [key, value] of arr.values())
    {
        console.log(value+" ");
    }
}

复杂度分析

• 时间复杂度：O(N)
• 空间复杂度：O(N)

[kangliqi1]

class Solution: def solve(self, root): q = collections.deque([(root, 0)]) d = {} while q: cur, pos = q.popleft() if pos not in d: d[pos] = cur.val if cur.left: q.append((cur.left, pos - 1)) if cur.right: q.append((cur.right, pos + 1)) return list(map(lambda x:x[1], sorted(d.items(),key=lambda x: x[0])))

[Hughlin07]

class Solution {

public int maxSubArray(int[] nums) {

    int sum = nums[0];
    int res = nums[0];

    for(int i = 1; i < nums.length; i++){
        sum = Math.max(nums[i], sum + nums[i]);
        res = Math.max(sum, res);

    }

    return res;
}

}

[JasonQiu]

• DFS

  class Solution:
  def verticalTraversal(self, root: Optional[TreeNode]) -> List[List[int]]:
      d_by_col = defaultdict(list)
  
      def dfs(node, row, col):
          if node:
              d_by_col[col].append((row, node.val))
              dfs(node.left, row + 1, col - 1)
              dfs(node.right, row + 1, col + 1)
  
      dfs(root, 0, 0)
  
      d_by_col_sorted = [n[1] for n in sorted(list(d_by_col.items()), key=lambda n: (n[0]))]
      result = []
      for col in d_by_col_sorted:
          result.append([n[1] for n in sorted(col, key=lambda n:(n[0], n[1]))])
      return result

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

[snmyj]

public void preOrderTraverse2(TreeNode root) {
        LinkedList<TreeNode> stack = new LinkedList<>();
        TreeNode pNode = root;
        while (pNode != null || !stack.isEmpty()) {
            if (pNode != null) {
                System.out.print(pNode.val+"  ");
                stack.push(pNode);
                pNode = pNode.left;
            } else { 
                TreeNode node = stack.pop();
                pNode = node.right;
            }
        }
    }

[Size-of]

class Solution: def solve(self, root): q = collections.deque([(root, 0)]) d = {} while q: cur, pos = q.popleft() if pos not in d: d[pos] = cur.val if cur.left: q.append((cur.left, pos - 1)) if cur.right: q.append((cur.right, pos + 1)) return list(map(lambda x:x[1], sorted(d.items(),key=lambda x: x[0])))

[Diana21170648]

思路

哈希表，BFS

代码

import collections
class Solution:
    def solve(self,root):
        q = collections.deque([(root,0)])
        d={}
        while q:
            current,posotion=q.popleft()
            if posotion  not in d:
                d[posotion]=current.value
                if current.left:
                    q.append(current,posotion-1)
                if current.right:
                    q.append(current.right,posotion+1)
        return list(map(lambda x:x[1],sorted(d.items(),key=lambda x:x[0])))

**复杂度分析**
- 时间复杂度：O(NlogN)，其中 N 为数组长度。
- 空间复杂度：O(N)

[Lydia61]

To-View-of-a-Tree

代码

class Solution:
    def solve(self, root):
        q = collections.deque([(root, 0)])
        d = {}
        while q:
            cur, pos = q.popleft()
            if pos not in d:
                d[pos] = cur.val
            if cur.left:
                q.append((cur.left, pos - 1))
            if cur.right:
                q.append((cur.right, pos + 1))
        return list(map(lambda x:x[1], sorted(d.items(), key=lambda x: x[0])))

复杂度分析

• 时间复杂度：O(nlogn)
• 空间复杂度：O(n)

[RestlessBreeze]

code

class Solution {
public:
    struct Node
    {
        int column;
        int row;
        int val;
        Node(int _val, int _row, int _column) : val(_val), row(_row), column(_column) {}
    };

    vector<Node*> v;
    void dfs(TreeNode* root, int row, int column)
    {
        if (!root) return;
        Node *n = new Node(root->val, row, column);
        v.push_back(n);
        dfs(root->left, row + 1, column - 1);
        dfs(root->right, row + 1, column + 1);
    }

    static bool cmp(Node* a, Node* b)
    {
        if (a->column != b->column) return a->column < b->column;
        if (a->row != b->row) return a->row < b->row;
        return a->val < b->val;
    }

    vector<vector<int>> verticalTraversal(TreeNode* root) {
        dfs(root, 0, 0);
        sort(v.begin(), v.end(), cmp);
        vector<vector<int>> res;

        int MAX = -1001;
        for (auto c : v)
        {
            if (c->column != MAX)
            {
                MAX = c->column;
                res.emplace_back();
            }
            res.back().push_back(c->val);
        }
        return res;
    }
};

[joemonkeylee]

思路

DFS

代码

   class Node
        {
            public int data;
            public Node left;
            public Node right;

            public Node(int key)
            {
                this.data = key;
                this.left = null;
                this.right = null;
            }
        }

        class Pair
        {
            public int hd;
            public Node node;
            public Pair(Node node, int hd)
            {
                this.node = node;
                this.hd = hd;
            }
        }

        List<int> topView(Node root)
        {
            Queue<Pair> q = new Queue<Pair>();
            Dictionary<int, int> map = new Dictionary<int, int>();
            List<int> arr = new List<int>();

            if (root == null) return arr;
            q.Enqueue(new Pair(root, 0));

            int min = 0;
            int max = 0;

            while (q.Count() != 0)
            {
                Pair x = q.Peek();
                if (!map.Keys.Contains(x.hd))
                {
                    map.Add(x.hd, x.node.data);
                }
                if (x.node.left != null)
                {
                    q.Enqueue(new Pair(x.node.left, x.hd - 1));
                    min = Math.Min(min, x.hd - 1);
                }
                if (x.node.right != null)
                {
                    q.Enqueue(new Pair(x.node.right, x.hd + 1));
                    max = Math.Max(max, x.hd + 1);
                }
            }

            for (int i = min; i <= max; i++)
            {
                arr.Add(map[i]);
            }
            return arr;
        }

复杂度分析

• 时间复杂度：O(nlogn)
• 空间复杂度：O(n)

[yingchehu]

leetcode 987

class Solution:
    def verticalTraversal(self, root: Optional[TreeNode]) -> List[List[int]]:
        seen = collections.defaultdict(lambda: collections.defaultdict(list))

        def dfs(node, x, y):
            if not node:
                return
            seen[x][y].append(node.val)
            dfs(node.left, x-1, y+1)
            dfs(node.right, x+1, y+1)

        dfs(root, 0, 0)
        ans = []

        for x in sorted(seen):
            column = []
            for y in sorted(seen[x]):
                for item in sorted(seen[x][y]):
                    column.append(item)
            ans.append(column)

        return ans

[X1AOX1A]

class Solution:
    def solve(self, root):
        q = collections.deque([(root, 0)])
        d = {}
        while q:
            cur, pos = q.popleft()
            if pos not in d:
                d[pos] = cur.val
            if cur.left:
                q.append((cur.left, pos - 1))
            if cur.right:
                q.append((cur.right, pos + 1))
        return list(map(lambda x:x[1], sorted(d.items(),key=lambda x: x[0])))

[Jetery]

987. 二叉树的垂序遍历

思路

本题可以理解为以根节点为(0, 0), 向左为(x + 1, y - 1), 向右为(x + 1, y + 1)
y值越小(列越靠前), x越小(层考前)的先入列
使用 map + multiset, y权重大于x, 以y值映射键值对(x, val)
通过前序遍历整颗树

代码 (cpp)

class Solution {
public:

    typedef map<int, multiset<pair<int, int>>> MAP;

    void trav(int x, int y, TreeNode* root, MAP &mp) {
        if (!root) return ;
        mp[y].insert({x, root->val});
        trav(x + 1, y - 1, root->left, mp);
        trav(x + 1, y + 1, root->right, mp);
    }

    vector<vector<int>> verticalTraversal(TreeNode* root) {
        MAP mp;
        trav(0, 0, root, mp);
        vector<vector<int>> ans;
        for (auto &[a, b] : mp) {
            vector<int> temp;
            for (auto &e : b) {
                temp.push_back(e.second);
            }
            ans.push_back(temp);
        }
        return ans;
    }
};

复杂度分析

• 时间复杂度：O(n)
• 空间复杂度：O(n)

[jmaStella]

思路

用自己的map的思路太复杂了，implement不好写 看了题解，都是逐级比较，override comparator更好写些。 new Comparator<int[]>(){ public int compare(int[] a, int[] b){ // do some comparsion return ; } };

代码

    public List<List<Integer>> verticalTraversal(TreeNode root) {
        List<int[]> nodes = new ArrayList<>();
        traverse(root, nodes, 0, 0);
        Collections.sort(nodes, new Comparator<int[]>(){
            public int compare(int[] a, int[] b){
                if(a[0]!= b[0]){
                    return a[0] - b[0];
                }else if(a[1] != b[1]){
                    return a[1] - b[1];
                }else{
                    return a[2] - b[2];
                }
            }
        });
        List<List<Integer>> result = new ArrayList<>();
        int col = Integer.MIN_VALUE;
        for(int[] node : nodes){
            if(col != node[0]){
                col = node[0];
                result.add(new ArrayList<>());
            }
            result.get(result.size() -1).add(node[2]);
        }
        return result;
    }
    public void traverse(TreeNode root, List<int[]> nodes, int row, int col){
        if(root == null){
            return;
        }
        nodes.add(new int[]{col, row, root.val});
        traverse(root.left, nodes, row+1, col-1);
        traverse(root.right, nodes, row+1, col+1);
    }

复杂度

时间 O(nlogn) 空间 O(n)