Leetcode #314:二叉樹的豎直周遊

• 題目
• • 題幹
  • 示例
• 題解
• • Python
  • C++

題目

題幹

該問題二叉樹的豎直周遊 題面：

Given a binary tree, return the vertical order traversal of its nodes’ values. (ie, from top to bottom, column by column).

If two nodes are in the same row and column, the order should be from left to right.

給定一個二叉樹，傳回其結點 垂直方向（從上到下，逐列）周遊的值。

如果兩個結點在同一行和列，那麼順序則為 從左到右。

示例

示例1：

輸入：

[3,9,20,null,null,15,7]

輸出：

[
 [9],
 [3,15],
 [20],
 [7]
]
           

示例2:

輸入:

[3,9,8,4,0,1,7]

輸出:

[
 [4],
 [9],
 [3,0,1],
 [8],
 [7]
]
           

示例3:

輸入:

[3,9,8,4,0,1,7,null,null,null,2,5]

(0’s right child is 2 and 1’s left child is 5)

輸出:

[
 [4],
 [9,5],
 [3,0,1],
 [8,2],
 [7]
]
           

題解

豎直周遊二叉樹并把每一列存入一個二維數組，示例1中，3和15屬于同一列，3在前，示例2中，3，0，1 在同一列，3在前，0和1緊随其後，那麼可以感覺到像是一種層序周遊的前後順序，如何來确定列的順序呢？可以把根節點給個序号0，然後開始層序周遊，凡是左子節點則序号減1，右子節點序号加1，這樣可以通過序号來把相同列的節點值放到一起，用一個TreeMap來建立序号和其對應的節點值的映射，用TreeMap的另一個好處是其自動排序功能可以讓列從左到右，由于層序周遊需要用到queue，此時queue 裡不能隻存節點，而是要存序号和節點組成的pair對兒，這樣每次取出就可以操作序号，而且排入隊中的節點也賦上其正确的序号。

Python

class BinaryTreeNode(object):
    def __init__(self, data, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right

    def __getitem__(self, key):
        return self.left if key == 0 else self.right

    def __setitem__(self, key, data):
        if (key == 0):
            self.left = data
        elif (key == 1):
            self.right = data

def initTree(elements: list, size: int):
    nodes = []
    for e in elements:
        if e == None:
            nodes.append(None)
        else:
            nodes.append(BinaryTreeNode(e))

    nodelist = [nodes[0]]
    index = 1
    while index < size:
        node = nodelist[0]
        nodelist.pop(0)
        nodelist.append(nodes[index])
        index += 1
        node.left = nodelist[-1]
        nodelist.append(nodes[index])
        index += 1
        node.right = nodelist[-1]
    return nodes[0]

class Solution:
    def __init__(self, root: BinaryTreeNode):
        self.root = root

    def veriticlaTree(self):
        res = []
        if self.root is None:
            return res
        m = {}
        q = [(0, self.root)]
        while len(q) != 0:
            a = q[0]
            q.pop(0）
            m.setdefault(a[0], []).append(a[1].data)
            if a[1].left:
                q.append((a[0]-1, a[1].left))
            if a[1].right:
                q.append((a[0]+1, a[1].right))
        for _,v in sorted(m.items()):
            res.append(v)
        return res
           

注意：

setdefault()

傳回的預設空清單是空清單的引用，改變傳回的清單值即改變字典的value，并且list.append()操作無傳回值，是以第50行如果使用

m[a[0]] = m.setdefault(a[0], []).append(a[1].data)

則會把

None

指派給字典，直接

append

就行無需指派。

C++

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

struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x):
        val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    vector<vector<int>> verticalOrder(TreeNode* root) {
        vector<vector<int>> res;
        if (!root) return res;
        map<int, vector<int>> m;
        queue<pair<int, TreeNode*>> q;
        q.push({0, root});
        while (!q.empty()) {
            auto a = q.front(); q.pop();
            m[a.first].push_back(a.second->val);
            if (a.second->left) q.push({a.first - 1, a.second->left});
            if (a.second->right) q.push({a.first + 1, a.second->right});
        }
        for (auto a : m) {
            res.push_back(a.second);
        }
        return res;
    }
};