【Day 53 】2022-05-23 - Top-View-of-a-Tree

[azl397985856]

Top-View-of-a-Tree

入选理由

暂无

题目地址

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

前置知识

• BFS
• 哈希表

  题目描述

  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

[zhiyuanpeng]

class Solution:
    def __init__(self):
        self.leftmost = 0
        self.rightmost = 0
        self.ans = {}

    def bfs(self, root):
        q = collections.deque([(root, 0)])
        self.ans[0] = root.val
        while len(q):
            cur_node, cur_col = q.popleft()
            if cur_col < self.leftmost:
                self.ans[cur_col] = cur_node.val
                self.leftmost = cur_col
            if cur_col > self.rightmost:
                self.ans[cur_col] = cur_node.val
                self.rightmost = cur_col
            if cur_node.left:
                q.append((cur_node.left, cur_col-1))
            if cur_node.right:
                q.append((cur_node.right, cur_col+1))

    def solve(self, root):
        self.bfs(root)
        self.ans = dict(sorted(self.ans.items()))
        return list(self.ans.values())

time O(NlogN) space O(N)

[JiangWenqi]

CPP + DFS

// col -> (row, val)
map<int, pair<int, int>> top_view;
void dfs(int row, int col, Tree* node) {
    if (node == NULL) return;

    if (!top_view.count(col) || top_view[col].first > row)
        top_view[col] = make_pair(row, node->val);

    dfs(row + 1, col - 1, node->left);
    dfs(row + 1, col + 1, node->right);
}
vector<int> solve(Tree* root) {
    top_view.clear();
    dfs(0, 0, root);
    vector<int> res;
    for (auto t : top_view) res.push_back(t.second.second);
    return res;
}

[xil324]

# 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):
        self.collection = {};
        self.collection[root.val] = (0,0); 
        self.helper(root); 
        used = []; 
        ans = []; 
        sorted_tuple = sorted(self.collection.items(),key = lambda x : (x[1][0], x[1][1])); 
        sorted_dict = {k:v for k,v in sorted_tuple}; 
        print(sorted_dict)
        for key in sorted_dict:
            if sorted_dict[key][0] in used: 
                continue;
            ans.append(key);
            used.append(sorted_dict[key][0])

        return ans; 

    def helper(self, root):
        if root is None:
            return; 
        if root.left:
            self.collection[root.left.val] = (self.collection[root.val][0]-1, self.collection[root.val][1] + 1); 
        if root.right: 
            self.collection[root.right.val] = (self.collection[root.val][0]+1, self.collection[root.val][1] + 1); 
        self.helper(root.left); 
        self.helper(root.right);

[zqwwei]

Code

class Solution {
    class TreeWithIdx {
        Tree node;
        int index;

        TreeWithIdx(Tree node, int index) {
            this.node = node;
            this.index = index;
        }

        Tree getNode() {
            return node;
        }

        int getIndex() {
            return index;
        }
    }

    private void bfs(Tree root, Map<Integer, Integer> idxToNode) {
        Queue<TreeWithIdx> q = new ArrayDeque<>();
        q.offer(new TreeWithIdx(root, 0));
        while (!q.isEmpty()) {
            TreeWithIdx tree = q.poll();
            Tree node = tree.getNode();
            int idx = tree.getIndex();
            if (!idxToNode.containsKey(idx)) {
                idxToNode.put(idx, node.val);
            }

            if (node.left != null) {
                q.offer(new TreeWithIdx(node.left, idx - 1));
            }

            if (node.right != null) {
                q.offer(new TreeWithIdx(node.right, idx + 1));
            }
        }
    }

    public int[] solve(Tree root) {
        Map<Integer, Integer> idxToNode = new TreeMap<>();
        bfs(root, idxToNode);
        List<Integer> resInList = new ArrayList<>();
        for (var nodeVal: idxToNode.values()) {
            resInList.add(nodeVal);
        }

        int [] ans = new int[resInList.size()];
        for (int i = 0; i < resInList.size(); ++i) {
            ans[i] = resInList.get(i);
        }

        return ans;
    }
}

Complexity

O(A log A + N) A is max number of nodes in a row, N is number of nodes

[Geek-LX]

5.23

思路：

• 哈希表
• 树
• BFS

代码：

# 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])))

复杂度分析:

时间复杂度O(nlogn)

空间复杂度为 O(n)

[xingchen77]

先打个卡

    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])))

[HuiWang1020]

Idea

HashMap + BFS

Code

class Solution {
    public int[] solve(Tree root) {
        List<Integer> list = new ArrayList<>();
        if (root == null)
        return null; 
        Queue<NodeObj> queue = new LinkedList<NodeObj>();
        Map<Integer,Integer> topView = new TreeMap<>();
        queue.add(new NodeObj(root, 0));

        while (!queue.isEmpty()) {
            NodeObj curr = queue.poll();
            Tree node = curr.node; 
            int hd = curr.hd;          

            if (!topView.containsKey(hd)) {
                topView.put(hd,node.val);
            }

            if (node.left != null) {
                queue.add(new NodeObj(node.left, hd - 1));
            }

            if (node.right != null) {
                queue.add(new NodeObj(node.right, hd + 1));
            }
        }

        for (Integer key : topView.keySet()) {
            list.add(topView.get(key));
        }
        int[] res = new int[list.size()];
        for (int i= 0; i < list.size(); i++) {
            res[i] = list.get(i);
        }
        return res;
    }
    class NodeObj  {
            Tree node;
            int hd; 
            NodeObj(Tree node, int hd)
            {
                this.node = node;
                this.hd = hd;
            }
   }
}

Complexity

time=o(nlogn) space=o(n)

[wenliangchen]

Idea

TreeMap + DFS

Code

class Solution {
    TreeMap<Integer, int[]> map = new TreeMap<>();
    List<Integer> list = new ArrayList<>();
    public int[] solve(Tree root) {
        dfs(root, 0, 0);

        for (int key : map.keySet()) {
            int pair[] = map.get(key);
            list.add(pair[0]);
        }

        int res[] = new int[list.size()];
        for (int i = 0; i < res.length; i++) {
            res[i] = list.get(i);
        }
        return res;
    }

    public void dfs(Tree root, int x, int level) {
        if (root == null)
            return;
        dfs(root.left, x - 1, level + 1);
        dfs(root.right, x + 1, level + 1);

        if (map.containsKey(x)) {
            int pair[] = map.get(x);
            if (pair[1] > level) {
                pair[1] = level;
                pair[0] = root.val;
            }
        } else {
            map.put(x, new int[] {root.val, level});
        }
    }
}

[houmk1212]

思路

BFS遍历树中节点，来方便管理高度（最高的才显示）。用额外的一个变量来记录左右的层次，并用哈希表存储结果。

代码

import java.util.*;

/**
 * public class Tree {
 *   int val;
 *   Tree left;
 *   Tree right;
 * }
 */
class Solution {
    int minLevel = Integer.MAX_VALUE;
    HashMap<Integer,Integer> map = new HashMap<>();
    public int[] solve(Tree root) {
        if (root == null){
            return new int[0];
        }

        bfs(root);
        int n = map.size();
        int[] res = new int[n];
        for (int i = 0; i < n; i++) {
            res[i] = map.get(minLevel++);
        }

        return res;
    }

    public void bfs(Tree root) {
        Deque<Pairs> queue = new ArrayDeque<>();
        queue.offer(new Pairs(root,0));
        while(!queue.isEmpty()) {
            int n = queue.size();
            for (int i = 0; i < n; i++) {
                Pairs p = queue.pop();
                minLevel = Math.min(minLevel,p.level);
                if (!map.containsKey(p.level)){
                    map.put(p.level,p.root.val);
                }
                if (p.root.left!=null) {
                    queue.offer(new Pairs(p.root.left,p.level-1));
                }
                if (p.root.right!=null) {
                    queue.offer(new Pairs(p.root.right,p.level+1));
                }
            }
        }
    }
}

class Pairs{
    Tree root;
    int level;

    public Pairs(Tree root, int level) {
        this.root = root;
        this.level = level;
    }
}

复杂度

• 时间复杂度：O（n）
• 空间复杂度：O（n）

[james20141606]

Day 53: 248. Top View of a Tree (search, BFS)

• Problem Link

  • 248. Top View of a Tree

• Ideas

  • we need to record x, y coordinate, and if the x coordinate is the same, a smaller y coordinate remains. We could also only record the x coordinate, if the x coordinate is seen, we do not need to update it. In the end we sort the result based on x coordinate

• Complexity: hash table and bucket

  • Time: O(NlogN) #sort algo
  • Space: O(N)

• Code

class Solution:
    def solve(self, root):
        q = collections.deque([(root, 0)]) #tuple here
        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))
        #print (d)
        return list(map(lambda x: x[1], sorted(d.items(), key = lambda x: x[0]))) 

• other resources:

[lxgang65]

打卡

void topView(Node * root) {
        if(root == nullptr)
            return;
        queue<pair<Node*,int>> q;
        map<int,Node*> top;
        q.push(make_pair(root,0));
        top[0]=root;
        while(!q.empty()){
            auto temp = q.front();
            q.pop();
            if(temp.first->left){
                q.push(make_pair(temp.first->left,temp.second-1));
                if(top.find(temp.second-1)==top.end())
                    top[temp.second-1]=temp.first->left;
            }
            if(temp.first->right){
                q.push(make_pair(temp.first->right,temp.second+1));
                if(top.find(temp.second+1)==top.end())
                    top[temp.second+1]=temp.first->right;
            }
        }
        for(auto x:top)
            cout<<x.second->data<<" ";
    }

[ZacheryCao]

Idea

BFS + HashTable

Code

# 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):
        if not root:
            return []
        record = {}
        left = 0
        right = 0
        stack = collections.deque()
        stack.append((root, 0))
        while stack:
            cur, index = stack.popleft()
            if index not in record:
                record[index] = cur.val
            left = min(left, index)
            right = max(right, index)
            if cur.left:
                stack.append((cur.left, index-1))
            if cur.right:
                stack.append((cur.right, index+1))
        ans = []
        for i in range(left, right+1):
            ans.append(record[i])
        return ans

Complexity:

Time: O(N) Space: O(N)

[ShawYuan97]

思路

使用一个字典，保存相应位置上的不同树节点，对于每个树节点保存层信息和val值
使用DFS来找到每个节点的位置和val值

关键点

• 深度优先搜索，带有左右位置信息和上下层间关系

代码

# 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):
        """
        返回二叉树的俯视图

        思路：
        采用先序遍历 记录每个节点的位置 
        """
        locate = collections.defaultdict(list)

        def dfs(root,x,layer):
            if not root:
                return 
            locate[x].append((layer,root.val))
            dfs(root.left,x-1,layer+1)
            dfs(root.right,x+1,layer+1)

        dfs(root,0,0)
        ans = []
        for l in sorted(locate):
            eles = locate[l]
            ans.append(sorted(eles)[0][1])
        return ans 

复杂度

令N为数节点个数 时间复杂度：遍历树$O(N)$，但是对横纵向排序复杂度为$O(Nlog(N))$ 空间复杂度：$O(N)$

[currybeefer]

打卡

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])))

[zjsuper]

key: dfs+dic to store pos of node

# 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):
        queue = collections.deque()
        queue.append((root,0))
        ans = []
        dic = {}
        while queue:
            node,pos = queue.popleft()
            if pos not in dic:
                dic[pos] = node.val
            if node.left:
                queue.append((node.left,pos-1))
            if node.right:
                queue.append((node.right,pos+1))  

        sorted_dict = {k: dic[k] for k in sorted(dic)} 
        return list(sorted_dict.values())    

[xiayuhui231]

代码

void topView(Node * root) {
        if(root == nullptr)
            return;
        queue<pair<Node*,int>> q;
        map<int,Node*> top;
        q.push(make_pair(root,0));
        top[0]=root;
        while(!q.empty()){
            auto temp = q.front();
            q.pop();
            if(temp.first->left){
                q.push(make_pair(temp.first->left,temp.second-1));
                if(top.find(temp.second-1)==top.end())
                    top[temp.second-1]=temp.first->left;
            }
            if(temp.first->right){
                q.push(make_pair(temp.first->right,temp.second+1));
                if(top.find(temp.second+1)==top.end())
                    top[temp.second+1]=temp.first->right;
            }
        }
        for(auto x:top)
            cout<<x.second->data<<" ";
    }

[zhishinaigai]

思路

BFS

代码

vector<int> solve(Tree* root) {
    map<int,int> m;
    queue<pair<int,Tree*>> q;
    q.push({0,root});
    while(!q.empty()){
        auto [f,s]=q.front();
        q.pop();
        if(m.count(f)==0) m[f]=s->val;
        if(s->left) q.push({f-1,s->left});
        if(s->right) q.push({f+1,s->right});
    }
    vector<int> ans;
    for(auto [f,s]:m) ans.push_back(s);
    return ans;
}

[carterrr]

public class 树的自顶向下视图 {

public int[] solve(TreeNode root){ Queue q = new LinkedList<>(); SortedMap<Integer, Integer> map = new TreeMap<>(); q.offer(new BFSNode(0, root)); map.put(0, root.val); while(!q.isEmpty()) { BFSNode cur = q.poll(); int vertical = cur.vertical; TreeNode left = cur.TreeNode.left; TreeNode right = cur.TreeNode.right;

  if(left != null) {
    BFSNode leftNode = new BFSNode(vertical - 1, left);
    if(!map.containsKey(vertical - 1)) {
      map.put(vertical - 1, left.val);
    }
    q.offer(leftNode);
  }

  if(right != null) {
    BFSNode rightNode = new BFSNode(vertical + 1, left);
    if(!map.containsKey(vertical + 1)) {
      map.put(vertical + 1, right.val);
    }
    q.offer(rightNode);
  }
}
int[] res = new int[map.size()];
int idx = 0;
for(int i : map.values()) {
  res[idx++] = i;
}
return res;

}

private class BFSNode{ int vertical; TreeNode TreeNode;

public BFSNode(int vertical,TreeNode TreeNode) {
  this.vertical = vertical;
  this.TreeNode = TreeNode;
}

}

}

[LQyt2012]

思路

BFS

代码

class Solution:
    def solve(self, root):
        queue = collections.deque()
        queue.append((root,0))
        ans = []
        dic = {}
        while queue:
            node,pos = queue.popleft()
            if pos not in dic:
                dic[pos] = node.val
            if node.left:
                queue.append((node.left,pos-1))
            if node.right:
                queue.append((node.right,pos+1))  

        sorted_dict = {k: dic[k] for k in sorted(dic)} 
        return list(sorted_dict.values())

复杂度分析

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

[miss1]

思路

BFS遍历每个节点，记录每个节点的col值，root的col为0，左子节点的col为col-1，右子节点的col为col+1；用col为key值，将tree存储到哈希表中。最后先将哈希表的key排序，再逐个获取哈希表中的值

代码

class Solution {
    solve(root) {
       let map = new Map();
       let keys = [];
       let currentLever = [[root,0]];
       while (currentLever.length > 0) {
           let nextLever = [];
           for (let i = 0; i < currentLever.length; i++) {
               let r = currentLever[i][0];
               let col = currentLever[i][1];
               if (!map.has(col)) {
                   map.set(col, r.val);
                   keys.push(col);
               }
               if (r.left) nextLever.push([r.left, col - 1]);
               if (r.right) nextLever.push([r.right, col + 1]);
           }
           currentLever = nextLever;
       }
       keys.sort((a,b) => a - b);
       let res = [];
       for (let i = 0; i < keys.length; i++) {
           res.push(map.get(keys[i]));
       }
       return res;
    }
}

复杂度

time: O(nlogn)

space: O(n)

[KWDFW]

Day53

剑指二094、二叉树的右侧视图

javascript #dfs

思路

1、遍历二叉树

2、建立一个level用来记录层数，确保每一层只有一个值

3、如果该层有右子树，则右子树的值会覆盖掉左子树。如果无右子树，则取左子树

代码

var rightSideView = function(root) {
  let res=[]//结果数组
  function dfs(node,level){//遍历二叉树
    if(!node) return//递归结束条件
    res[level]=node.val 
    dfs(node.left,level+1)
    dfs(node.right,level+1)
    //先后遍历左右节点，右节点的值会覆盖左节点
  }
  dfs(root,0)
  return res
};

复杂度分析

时间复杂度：O(nlogn)

空间复杂度：O(1)

[KennethAlgol]

class Solution {
    public int[] solve(Tree root) {
        List<Integer> list = new ArrayList<>();
        if (root == null)
        return null; 
        Queue<NodeObj> queue = new LinkedList<NodeObj>();
        Map<Integer,Integer> topView = new TreeMap<>();
        queue.add(new NodeObj(root, 0));

        while (!queue.isEmpty()) {
            NodeObj curr = queue.poll();
            Tree node = curr.node; 
            int hd = curr.hd;          

            if (!topView.containsKey(hd)) {
                topView.put(hd,node.val);
            }

            if (node.left != null) {
                queue.add(new NodeObj(node.left, hd - 1));
            }

            if (node.right != null) {
                queue.add(new NodeObj(node.right, hd + 1));
            }
        }

        for (Integer key : topView.keySet()) {
            list.add(topView.get(key));
        }
        int[] res = new int[list.size()];
        for (int i= 0; i < list.size(); i++) {
            res[i] = list.get(i);
        }
        return res;
    }
    class NodeObj  {
            Tree node;
            int hd; 
            NodeObj(Tree node, int hd)
            {
                this.node = node;
                this.hd = hd;
            }
   }
}

[Orangejuz]

# 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])))

[dtldtt]

2022-05-10

leetcode侧视图

代码

class Solution
{
public:
    vector<int> rightSideView( TreeNode* root )
    {
        vector<int> view; // view[i] 表示第i层的最后一个节点，i从0开始
        if ( !root )
            return view;

        // 队列中的元素是 <节点， 层数>
        queue< pair< TreeNode*, int > > Q;

        if ( root )
            Q.push( make_pair(root, 0) );

        while ( !Q.empty() )
        {
            // 记录一下首元素，然后将其弹出
            TreeNode* node = Q.front().first;
            int depth = Q.front().second;
            Q.pop();

            // 对view的更新，有两种情况
            // 1）view[i] 还没有，直接push即可
            // 2）view[i] 已经存在，但不是最右边的值，需要将其替换
            if ( view.size() == depth)
                view.push_back( node->val );
            else
            {
                // view.pop_back();
                // view.push_back( node->val );
                view[view.size() - 1] = node->val;
            }

            if ( node->left )
                Q.push( make_pair( node->left, depth + 1));
            if ( node->right )
                Q.push( make_pair( node->right, depth + 1));
        }
        return view;
    }
};

备注

[houyanlu]

思路

BFS 这是做的是leetcode right view

代码

/**
 * 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> ret;
        deque <TreeNode*> q;

        if (root == nullptr) {
            return ret;
        }

        q.push_back(root);
        while (!q.empty()) {
            int n = q.size();
            for (int i = 0; i < n; ++i) {
                TreeNode *node = q.front();
                q.pop_front();

                if (i == n - 1) {
                    ret.push_back(node->val);
                }

                if (node->left) {
                    q.push_back(node->left);
                }

                if (node->right) {
                    q.push_back(node->right);
                }
            }
        }

        return ret;

    }
};

复杂度分析

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

[Shuchunyu]

HashMap + BFS

Code class Solution { public int[] solve(Tree root) { List list = new ArrayList<>(); if (root == null) return null; Queue queue = new LinkedList(); Map<Integer,Integer> topView = new TreeMap<>(); queue.add(new NodeObj(root, 0));

    while (!queue.isEmpty()) {
        NodeObj curr = queue.poll();
        Tree node = curr.node; 
        int hd = curr.hd;          

        if (!topView.containsKey(hd)) {
            topView.put(hd,node.val);
        }

        if (node.left != null) {
            queue.add(new NodeObj(node.left, hd - 1));
        }

        if (node.right != null) {
            queue.add(new NodeObj(node.right, hd + 1));
        }
    }

    for (Integer key : topView.keySet()) {
        list.add(topView.get(key));
    }
    int[] res = new int[list.size()];
    for (int i= 0; i < list.size(); i++) {
        res[i] = list.get(i);
    }
    return res;
}
class NodeObj  {
        Tree node;
        int hd; 
        NodeObj(Tree node, int hd)
        {
            this.node = node;
            this.hd = hd;
        }

} }

[MichaelXi3]

Idea

• HashMap + BFS

  Code

  class Solution {
  public int[] solve(Tree root) {
      if (root == null) {
          return new int[0];
      }
      HashMap<Integer, Integer> map = new HashMap<>();
      Queue<Tree> q = new LinkedList<>();
      Queue<Integer> index = new LinkedList<>();
      int min_id = 0;
      q.offer(root);
      index.offer(0);
  
      while (!q.isEmpty()) {
          Tree curr = q.poll();
          int id = index.poll();
          if (!map.containsKey(id)) {
              map.put(id, curr.val);
              min_id = Math.min(min_id, id);
          }
  
          if (curr.left != null) {
              q.offer(curr.left);
              index.offer(id - 1);
          }
  
          if (curr.right != null) {
              q.offer(curr.right);
              index.offer(id + 1);
          }
      }
  
      int n = map.size();
      int res[] = new int[n];
      for (Map.Entry<Integer, Integer> e : map.entrySet()) {
          res[e.getKey() - min_id] = e.getValue();
      }
  
      return res;
  }
  }

  Complexity

• Time O(n)
• Space O(n)

[ShuqianYang]

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])))

[freedom0123]

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        if(root == null){
            return new ArrayList<>();
        }
        List<Integer> res = new ArrayList<>();
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()){
            int size = queue.size();
            TreeNode first = new TreeNode();
            for(int i = 0;i<size;i++){
                first = queue.getFirst();
                queue.removeFirst();
                if(first.left!=null){
                    queue.add(first.left);
                }
                if(first.right!=null){
                    queue.add(first.right);
                }
            }
            res.add(first.val);
        }

        return res;

    }
}

[rzhao010]

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    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];
        });
        int n = list.size();
        List<List<Integer>> res = new ArrayList<>();
        for (int i = 0; i < n;) {
            int j = i;
            List<Integer> tmp = new ArrayList<>();
            while (j < n && list.get(j)[0] == list.get(i)[0]) {
                tmp.add(list.get(j++)[2]);
            }
            res.add(tmp);
            i = j;
        }
        return res;
    }

    private void dfs(TreeNode root) {
        if (root == null) return;

        int[] info = map.get(root);
        int col = info[0], row = info[1], val = 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);
        }
    }
}

[wychmod]

思路

主要还是二叉树的暴力递归，同时要结合哈希表

代码

class Solution:
    def solve(self, root):
        seen = collections.defaultdict(dict)
        def dfs(root, x, y):
            if not root:
                return
            if seen[x].get(y, None) == None:
                seen[x][y] = root.val
            dfs(root.left, x-1, y+1)
            dfs(root.right, x+1, y+1)

        dfs(root, 0, 0)
        ans = []
        for x in sorted(seen):
            y = min(seen[x].keys())
            ans.append(seen[x][y])
        return ans

[XXjo]

思路

BFS

代码

var solve = function(root){
    let q = [[root, 0]];
    let hashmap = new Map();
    while(q.length > 0){
        let [curNode, curPos] = q.shift();
        if(!hashmap.has(curPos)){
            hashmap.set(curPos, curNode);
        }
        if(curNode.left !== null){
            q.push([curNode.left, curPos - 1]);
        }
        if(curNode.right !== null){
            q.push([curNode.left, curPos + 1]);
        }
    }
    //根据key排序
    let sortedKeys = Array.from(hashmap.keys()).sort((a, b) => a - b);
    let res = [];
    for(let key of sortedKeys){
        res.push(hashmap.get(key).val)
    }
    return res;
}

[taojin1992]

import java.util.*;

/**
 * public class Tree {
 *   int val;
 *   Tree left;
 *   Tree right;
 * }
 */
class Solution {
    class Wrapper {
        int x;
        Tree node;

        Wrapper(int x, Tree node) {
            this.x = x;
            this.node = node;
        }
    }
    public int[] solve(Tree root) {
        if (root == null) return new int[0];

        LinkedList<Integer> view = new LinkedList<>();
        view.add(root.val);
        int minX = 0, maxX = 0;
        Queue<Wrapper> queue = new LinkedList<>();
        queue.offer(new Wrapper(0, root));

        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                Wrapper cur = queue.poll();
                int curX = cur.x;
                Tree curNode = cur.node;
                if (curNode.left != null) {
                    queue.offer(new Wrapper(curX - 1, curNode.left));
                }
                if (curNode.right != null) {
                    queue.offer(new Wrapper(curX + 1, curNode.right));
                }
                if (curX < minX) {
                    view.addFirst(curNode.val);
                    minX = curX;
                }
                if (curX > maxX) {
                    view.addLast(curNode.val);
                    maxX = curX;
                }
            }
        }
        int[] res = new int[view.size()];
        for (int i = 0; i < view.size(); i++) {
            res[i] = view.get(i);
        }
        return res;
    }
}

[AConcert]

var rightSideView = function(root) {
  let res=[]
  function dfs(node,level){
    if(!node) return
    res[level]=node.val 
    dfs(node.left,level+1)
    dfs(node.right,level+1)
  }
  dfs(root,0)
  return res
};

[tensorstart]

思路

抄的

代码

class Solution {
    solve(root) {
       let map = new Map();
       let keys = [];
       let currentLever = [[root,0]];
       while (currentLever.length > 0) {
           let nextLever = [];
           for (let i = 0; i < currentLever.length; i++) {
               let r = currentLever[i][0];
               let col = currentLever[i][1];
               if (!map.has(col)) {
                   map.set(col, r.val);
                   keys.push(col);
               }
               if (r.left) nextLever.push([r.left, col - 1]);
               if (r.right) nextLever.push([r.right, col + 1]);
           }
           currentLever = nextLever;
       }
       keys.sort((a,b) => a - b);
       let res = [];
       for (let i = 0; i < keys.length; i++) {
           res.push(map.get(keys[i]));
       }
       return res;
    }
}

[revisegoal]

bfs

• 构建一个类可以放节点和其坐标，题意可视为bfs遍历时保存第一个x坐标的节点值（后面相同x坐标被第一个挡住），然后按x顺序输出
• 可以使用TreeMap用x坐标存储对应节点值，同时x顺序也得到维护
• y坐标其实可以不用保存

  
  import java.util.*;

/**

• public class Tree {
• int val;
• Tree left;
• Tree right;
• } */ class Solution { class Helper { Tree tree; int x; int y; Helper(Tree tree, int x, int y) { this.tree = tree; this.x = x; this.y = y; } } public int[] solve(Tree root) { Queue queue = new LinkedList<>(); Map<Integer, Integer> map = new TreeMap<>(); queue.offer(new Helper(root, 0, 0)); while (!queue.isEmpty()) { int size = queue.size(); for (int i = 0; i < size; i++) { Helper helper = queue.poll(); Tree tree = helper.tree; int x = helper.x; int y = helper.y; if (!map.containsKey(x)) { map.put(x, tree.val); } if (tree.left != null) { queue.offer(new Helper(tree.left, x - 1, y + 1)); } if (tree.right != null) { queue.offer(new Helper(tree.right, x + 1, y + 1)); } } } int[] res = new int[map.size()]; int i = 0; for (Map.Entry<Integer, Integer> entry: map.entrySet()) { res[i++] = entry.getValue(); } return res; } }

  
  - time: O(n)
  - space: O(n)

[Magua-hub]

class Solution:
    def solve(self, root):
        seen = collections.defaultdict(dict)
        def dfs(root, x, y):
            if not root:
                return
            if seen[x].get(y, None) == None:
                seen[x][y] = root.val
            dfs(root.left, x-1, y+1)
            dfs(root.right, x+1, y+1)

        dfs(root, 0, 0)
        ans = []
        for x in sorted(seen):
            y = min(seen[x].keys())
            ans.append(seen[x][y])
        return ans

[maggiexie00]

def solve(self, root):
    q = deque([(root, 0)])
    x = {}
    while q:
        (node, xval) = q.popleft()
        if xval not in x:
            x[xval] = node.val
        if node.left:
            q.append((node.left, xval - 1))
        if node.right:
            q.append((node.right, xval + 1))
    return [j for (i, j) in sorted(list(x.items()))]

[xixiao51]

Idea

HashMap + BFS

Code

class Solution {
    public int[] solve(Tree root) {
        List<Integer> list = new ArrayList<>();
        if (root == null)
        return null; 
        Queue<NodeObj> queue = new LinkedList<NodeObj>();
        Map<Integer,Integer> topView = new TreeMap<>();
        queue.add(new NodeObj(root, 0));

        while (!queue.isEmpty()) {
            NodeObj curr = queue.poll();
            Tree node = curr.node; 
            int hd = curr.hd;          

            if (!topView.containsKey(hd)) {
                topView.put(hd,node.val);
            }

            if (node.left != null) {
                queue.add(new NodeObj(node.left, hd - 1));
            }

            if (node.right != null) {
                queue.add(new NodeObj(node.right, hd + 1));
            }
        }

        for (Integer key : topView.keySet()) {
            list.add(topView.get(key));
        }
        int[] res = new int[list.size()];
        for (int i= 0; i < list.size(); i++) {
            res[i] = list.get(i);
        }
        return res;
    }
    class NodeObj  {
            Tree node;
            int hd; 
            NodeObj(Tree node, int hd)
            {
                this.node = node;
                this.hd = hd;
            }
   }
}

Complexity

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

[flyzenr]

class Solution:
    def solve(self, root):
        seen = collections.defaultdict(dict)
        def dfs(root, x, y):
            if not root:
                return
            if seen[x].get(y, None) == None:
                seen[x][y] = root.val
            dfs(root.left, x-1, y+1)
            dfs(root.right, x+1, y+1)

        dfs(root, 0, 0)
        ans = []
        for x in sorted(seen):
            y = min(seen[x].keys())
            ans.append(seen[x][y])
        return ans

[linjunhe]

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])))

[weihaoxie]

思路

BFS+哈希表

代码

# 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])))

复杂度

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

[gitbingsun]

/**

• class Tree {
• public:
• int val;
• Tree *left;
• Tree *right;
• }; / void updateNode(queue<pair<Tree,int>>& q, map<int, int>& widthMap, int w, Tree* node) { q.push({node, w}); if (widthMap.find(w) == widthMap.end()) { widthMap.insert({w, node->val}); }

}

vector solve(Tree root) { map<int, int> widthMap; // width --> node value queue<pair<Tree,int>> q; // node --> width

if (root != nullptr) {
    q.push({root, 0});
    widthMap.insert({0, root->val});
}

while (!q.empty()) {
    int qsize = q.size();
    auto p = q.front(); q.pop();
    int w = p.second;
    Tree* v = p.first;

    if (v->left != nullptr)
        updateNode(q, widthMap, w-1, v->left);

    if (v->right != nullptr)
        updateNode(q, widthMap, w+1, v->right);
}

vector<int> res;
map<int, int>::iterator it;
for (it = widthMap.begin(); it != widthMap.end(); it++) {
    res.push_back(it->second);
}
return res;

}