# 314.Binary-Tree-Vertical-Order-Traversal

## 314. Binary Tree Vertical Order Traversal

## 题目地址

<https://leetcode.com/problems/binary-tree-vertical-order-traversal/>

## 题目描述

```
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.

Examples 1:

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

   3
  /\
 /  \
 9  20
    /\
   /  \
  15   7 

Output:

[
  [9],
  [3,15],
  [20],
  [7]
]
Examples 2:

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

     3
    /\
   /  \
   9   8
  /\  /\
 /  \/  \
 4  01   7 

Output:

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

## 代码

Approach 1\[Accpeted]: DFS

1. Traverse to find the minimum and maximum vertical levels
2. 双Queue进行DFS层序遍历，另一个Queue放level

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    int min, max;
    public List<List<Integer>> verticalOrder(TreeNode root) {
        findMinMax(root, 0);
        List<List<Integer>> ans = new ArrayList<>();
    if (root == null) return ans;

        for (int i = min; i <= max; i++) {
            List<Integer> list = new ArrayList<Integer>();
            ans.add(list);
        }

        Queue<TreeNode> nodeQ = new LinkedList<TreeNode>();
        Queue<Integer> levelQ = new LinkedList<Integer>();
        nodeQ.add(root);
        levelQ.add(0 - min);
        while (!nodeQ.isEmpty()) {
            int size = nodeQ.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = nodeQ.poll();
                int index = levelQ.poll();
                List<Integer> list = ans.get(index);
                list.add(node.val);

                if (node.left != null) {
                    nodeQ.add(node.left);
                    levelQ.add(index - 1);
                }
                if (node.right != null) {
                    nodeQ.add(node.right);
                    levelQ.add(index + 1);
                }
            }
        }
        return ans;
    }

    void findMinMax(TreeNode root, int hd) {
        if (root == null)    return;

        if (hd < min) {
            min = hd;
        }
        if (hd > max) {
            max = hd;
        }

        findMinMax(root.left, hd - 1);
        findMinMax(root.right, hd + 1);
    }

}
```

Approach 2\[Rejected]: preorder Iterative

```java
class Solution {
    int min, max;
    public List<List<Integer>> verticalOrder(TreeNode root) {
        findMinMax(root, 0);
        List<List<Integer>> ans = new ArrayList<>();
        for (int i = min; i <= max; i++) {
            List<Integer> list = new ArrayList<Integer>();
            ans.add(list);
        }

    Stack<TreeNode> stack = new Stack<TreeNode>();
        Stack<Integer> indexStack = new Stack<Integer>();
        stack.push(root);
        indexStack.push(0);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            int index = indexStack.pop();
            List<Integer> list = ans.get(index - min);

            System.out.print(" " + node.val);
            list.add(node.val);

            if (node.right != null) {
                stack.push(node.right);
                indexStack.push(index + 1);
            }

            if (node.left != null) {
                stack.push(node.left);
                indexStack.push(index - 1);
            }

        }

            return ans;
    }

    void findMinMax(TreeNode root, int hd) {
        if (root == null)    return;

        if (hd < min) {
            min = hd;
        }
        if (hd > max) {
            max = hd;
        }

        findMinMax(root.left, hd - 1);
        findMinMax(root.right, hd + 1);
    }
}
```

Approach 3\[Rejected]: preorder in Recursion

```java
class Solution {
    int min;
    int max;
    public List<List<Integer>> verticalOrder(TreeNode root) {

        findMinMax(root, 0);
        List<List<Integer>> ans = new ArrayList<>();
        for (int i = min; i <= max; i++) {
            List<Integer> list = new ArrayList<Integer>();
            traverseVerticalNode(root, i, 0, list);
            ans.add(list);
        }

        return ans;
    }

    void findMinMax(TreeNode root, int hd) {
        if (root == null)    return;

        if (hd < min) {
            min = hd;
        }
        if (hd > max) {
            max = hd;
        }

        findMinMax(root.left, hd - 1);
        findMinMax(root.right, hd + 1);
    }

    void traverseVerticalNode(TreeNode root, int line, int hd, List<Integer> list) {
        if (root == null) return;

        if (line == hd) {
            list.add(root.val);
        }

        traverseVerticalNode(root.left, line, hd - 1, list);
        traverseVerticalNode(root.right, line, hd + 1, list);
    }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://wentao-shao.gitbook.io/leetcode/data-structure/314.binary-tree-vertical-order-traversal.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.