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

題目描述

給你二叉樹的根結點 root ，請你設計算法計算二叉樹的 垂序遍歷 序列。

對位于?(row, col)?的每個結點而言，其左右子結點分別位于?(row + 1, col - 1)?和?(row + 1, col + 1) 。樹的根結點位于 (0, 0) 。

二叉樹的 垂序遍歷 從最左邊的列開始直到最右邊的列結束，按列索引每一列上的所有結點，形成一個按出現位置從上到下排序的有序列表。如果同行同列上有多個結點，則按結點的值從小到大進行排序。

返回二叉樹的 垂序遍歷 序列。

?

?解題思路

第一步：計算出所有節點的坐標

第二步：按照順序輸出這些坐標所對應的值

解題代碼

package com.yucheng;import java.util.ArrayList; import java.util.Collections; import java.util.List; import java.util.Stack;public class Solution987 {public static void main(String[] args) {TreeNode n20 = new TreeNode(15);TreeNode n22 = new TreeNode(7);TreeNode n11 = new TreeNode(20, n20, n22);TreeNode n_11 = new TreeNode(9);TreeNode root = new TreeNode(3, n_11, n11);Solution987 solution987 = new Solution987();System.out.println(solution987.verticalTraversal(root));}public List<List<Integer>> verticalTraversal(TreeNode root) {Stack<MyTreeNode> stack = new Stack<>();MyTreeNode newRoot = new MyTreeNode(root, 0, 0);stack.push(newRoot);Res[][] res = new Res[1000][2000];res[0][1000] = new Res();res[0][1000].list.add(root.val);while (!stack.empty()) {MyTreeNode father = stack.pop();if (father.treeNode.left != null) {MyTreeNode l = new MyTreeNode(father.treeNode.left, father.x + 1, father.y - 1);if (res[l.x][l.y + 1000] == null) {res[l.x][l.y + 1000] = new Res();}res[l.x][l.y + 1000].list.add(l.treeNode.val);stack.push(l);}if (father.treeNode.right != null) {MyTreeNode r = new MyTreeNode(father.treeNode.right, father.x + 1, father.y + 1);if (res[r.x][r.y + 1000] == null) {res[r.x][r.y + 1000] = new Res();}res[r.x][r.y + 1000].list.add(r.treeNode.val);stack.push(r);}}List<List<Integer>> ans = new ArrayList<>();for (int j = 0; j < 2000; j++) {ArrayList<Integer> line = new ArrayList<>();for (int i = 0; i < 1000; i++) {if (res[i][j] != null) {Collections.sort(res[i][j].list);line.addAll(res[i][j].list);}}if (line.size() != 0) {ans.add(line);}}return ans;}}class MyTreeNode {TreeNode treeNode;int x;int y;MyTreeNode(TreeNode treeNode, int x, int y) {this.treeNode = treeNode;this.x = x;this.y = y;}}class Res {ArrayList<Integer> list;public Res() {this.list = new ArrayList<>();}}

總結

以上是生活随笔為你收集整理的Leetcode987 二叉树的垂序遍历的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。