【LeetCode】987.Vertical Order Traversal of a Binary Tree解題報告(C+&Python)

作者:負雪明ろうそくid:fuxuemingzhu個人ブログ:http://fuxuemingzhu.cn/
目次

タイトル説明

テーマ大意

解題方法

DFS

BFS

日付

タイトルアドレス:https://leetcode.com/problems/vertical-order-traversal-of-a-binary-tree/
タイトルの説明
Given a binary tree, return the vertical order traversal of its nodes values.
For each node at position (X, Y) , its left and right children respectively will be at positions (X-1, Y-1) and (X+1, Y-1) .
Running a vertical line from X = -infinity to X = +infinity , whenever the vertical line touches some nodes, we report the values of the nodes in order from top to bottom (decreasing Y coordinates).
If two nodes have the same position, then the value of the node that is reported first is the value that is smaller.
Return an list of non-empty reports in order of X coordinate. Every report will have a list of values of nodes.
Example 1:

Input: [3,9,20,null,null,15,7]
Output: [[9],[3,15],[20],[7]]
Explanation: 
Without loss of generality, we can assume the root node is at position (0, 0):
Then, the node with value 9 occurs at position (-1, -1);
The nodes with values 3 and 15 occur at positions (0, 0) and (0, -2);
The node with value 20 occurs at position (1, -1);
The node with value 7 occurs at position (2, -2).

Example 2:

Input: [1,2,3,4,5,6,7]
Output: [[4],[2],[1,5,6],[3],[7]]
Explanation: 
The node with value 5 and the node with value 6 have the same position according to the given scheme.
However, in the report "[1,5,6]", the node value of 5 comes first since 5 is smaller than 6.

Note:

The tree will have between 1 and 1000 nodes.

Each node’s value will be between 0 and 1000 .

テーマの大意
1つの二叉木が左から右に縦に見て、各列の結果を一緒に置くと、結果はどのようになりますか.
規定:1つのノードの水平方向の位置はXであり、垂直方向の高さはYであり、その座標は(X, Y)である.では、その左右の子供の座標はそれぞれ(X-1, Y-1) and (X+1, Y-1)である.
すなわち,同じXのノード位置を一緒にし,結果としてノードの格納を上から下にすることが要求される.2つのノードの座標が同じ場合、valueの小さいノードが前に並んでいます.
解題方法
DFS
最も率直な方法は,各ノードの位置を求め,問題要求の配列方式を構築することである.便宜上、私たちは求める過程で同じX値を一緒に置いて、同時にY座標と値を保存します.
だから、mapを定義しました.このMapの構造はmap>>で、x==>(-y,value)のマッピングが保存されています.したがって、DFSを行う過程で、各座標に座標(X,Y)を記録し、その座標に基づいて同じXを一緒に配置します.なぜ-yを使うのですか?これは,ノードのY座標がより小さいことを問題で教えてくれ,問題が要求するYソートは上から下への順であるからである.ルートノード層のY座標を0に設定すると、下の各層の真のY値は-1,-2,-3......、私たちのsort関数はデフォルトでインクリメンタルソートされるので、sortの便利さのためにvectorに置かれるのは-yです.
同じXのすべての(-y,value)対を求めた後,Y値が厳密に増加するようにソートし,Y値が同じ場合にvalue値でソートした.並べ替えたノードのvalue値をすべて取り出して結果に入れればよい.
注目されない点は、nodeMapがunordered_ではなくmapデータ構造を使用する必要があることです.map.mapは秩序を保証するので、つまりnodeMapを巡るとき、Xはすでにソートされています.unordered_mapは無秩序構造であり,遍歴はXが秩序であることを保証せず,面倒を増大させる.
もう1つのC++の知識点は、for (auto nm : nodeMap)を使用する場合、nmはポインタではなく複製されたオブジェクトであるため、nm->secondを使用するのではなく、nm.secondを使用すべきである.
時間的複雑度はO(N＋N＊(N＊log(N)＋N))である.1つ目のNはDFSが各ノードを1回遍歴することである.forループには層Nがあり,ループの中には層ソートがNlognであり,遍歴はNである).
空間複雑度はO(N)である.
C++コードは以下の通りです.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> verticalTraversal(TreeNode* root) {
        nodeMap.clear();
        dfs(root, 0, 0);
        vector<vector<int>> res;
        for (auto nm : nodeMap) {
            sort(nm.second.begin(), nm.second.end());
            vector<int> cols;
            for (auto p : nm.second)            
                cols.push_back(p.second);
            res.push_back(cols);
        }
        return res;
    }
private:
    map<int, vector<pair<int, int>>> nodeMap; // x ==> (-y, value)
    void dfs(TreeNode* root, int x, int y) {
        if (!root) return;
        nodeMap[x].emplace_back(-y, root->val);
        dfs(root->left, x - 1, y - 1);
        dfs(root->right, x + 1, y - 1);
    }
};

次のpythonコードは辞書ではなくlistで(x,-y,value)三元グループを保存する方式でsortを直接使用してソートできます.このようなトラブルは、前後の2つの隣接する3元グループに対応するx値が等しいかどうかを比較して、同じ列のlistに格納されるかどうかを判断する必要があり、コードは以下の通りである.

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def verticalTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        self.m_ = list()
        self.dfs(root, 0, 0)
        self.m_.sort()
        res = [[self.m_[0][2]]]
        for i in range(1, len(self.m_)):
            if self.m_[i][0] == self.m_[i - 1][0]:
                res[-1].append(self.m_[i][2])
            else:
                res.append([self.m_[i][2]])
        return res
        
    def dfs(self, root, x, y):
        if not root: return
        self.m_.append((x, -y, root.val))
        self.dfs(root.left, x - 1, y - 1)
        self.dfs(root.right, x + 1, y - 1)

BFS
この問題もBFSを用いて解決することができ,キューを維持することによって,各ノードを上から下へ順に遍歴し,各ノードに座標を設定した.このキューに格納されているトリプルグループ(TreeNode*,int x,int y)のやり方はDFSの方法と極めて類似しており,詳細は後述しない.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> verticalTraversal(TreeNode* root) {
        queue<pair<TreeNode*, pair<int, int>>> q; // node, x, y
        q.push(make_pair(root, make_pair(0, 0)));
        map<int, vector<pair<int, int>>> nodeMap;
        while (!q.empty()) {
            auto d = q.front(); q.pop();
            TreeNode* curNode = d.first;
            int x = d.second.first;
            int y = d.second.second;
            nodeMap[x].emplace_back(-y, curNode->val);
            if (curNode->left)
                q.push(make_pair(curNode->left, make_pair(x - 1, y - 1)));
            if (curNode->right)
                q.push(make_pair(curNode->right, make_pair(x + 1, y - 1)));
        }
        vector<vector<int>> res;
        for (auto nm : nodeMap) {
            sort(nm.second.begin(), nm.second.end());
            vector<int> cols;
            for (auto p : nm.second)
                cols.push_back(p.second);
            res.push_back(cols);
        }
        return res;
    }
};

pythonバージョンのBFSは,同様に,すべてのノードを1回遍歴して各ノードの位置を保存し,位置に基づいて遍歴解を並べ替える方式で行われている.

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def verticalTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        q = collections.deque()
        q.append((root, 0, 0))
        m_ = list()
        while q:
            node, x, y = q.popleft()
            m_.append((x, -y, node.val))
            if node.left:
                q.append((node.left, x - 1, y - 1))
            if node.right:
                q.append((node.right, x + 1, y - 1))
        m_.sort()
        res = [[m_[0][2]]]
        for i in range(1, len(m_)):
            if m_[i][0] == m_[i - 1][0]:
                res[-1].append(m_[i][2])
            else:
                res.append([m_[i][2]])
        return res

日付
2019年2月20日——知識を少なくして問題を多くする