Skip to content

Latest commit

 

History

History
225 lines (179 loc) · 6.92 KB

README.md

File metadata and controls

225 lines (179 loc) · 6.92 KB
comments difficulty edit_url tags
true
中等
栈
树
深度优先搜索
二叉树

2764. 数组是否表示某二叉树的前序遍历 🔒

English Version

题目描述

给定一个以 0 为起始索引的整数 二维数组 nodes ，你的任务是确定给定的数组是否表示某个 二叉 树的 前序 遍历。

对于每个索引 i ，nodes[i] = [id, parentId] ，其中 id 是索引 i 处节点的 id，parentId 是其在树中的父节点 id（如果该节点没有父节点，则 parentId = -1 ）。

如果给定的数组表示某个树的前序遍历，则返回 true ，否则返回 false 。

注意：树的 前序 遍历是一种递归的遍历方式，它首先访问当前节点，然后对左子节点进行前序遍历，最后对右子节点进行前序遍历。

 

示例 1：

输入：nodes = [[0,-1],[1,0],[2,0],[3,2],[4,2]]
输出：true
解释：给定的 nodes 数组可以构成下面图片中的树。 
我们可以验证这是树的前序遍历，首先访问节点 0，然后对左子节点进行前序遍历，即 [1] ，然后对右子节点进行前序遍历，即 [2,3,4] 。

示例 2：

输入：nodes = [[0,-1],[1,0],[2,0],[3,1],[4,1]]
输出：false
解释：给定的 nodes 数组可以构成下面图片中的树。 
对于前序遍历，首先访问节点 0，然后对左子节点进行前序遍历，即 [1,3,4]，但是我们可以看到在给定的顺序中，2 位于 1 和 3 之间，因此它不是树的前序遍历。

 

提示：

  • 1 <= nodes.length <= 105
  • nodes[i].length == 2
  • 0 <= nodes[i][0] <= 105
  • -1 <= nodes[i][1] <= 105
  • 生成的输入保证 nodes 可以组成二叉树。

解法

方法一：DFS

我们先根据 $nodes$ 数据构建图 $g$，其中 $g[i]$ 表示节点 $i$ 的所有子节点。

接下来，设计一个函数 $dfs(i)$，表示从节点 $i$ 开始进行先序遍历，用一个变量 $k$ 表示当前遍历到 $nodes$ 列表的第 $k$ 个节点，初始时 $k=0$。

函数 $dfs(i)$ 的执行逻辑如下：

  • 如果 $i \neq nodes[k][0]$，说明当前序列不是二叉树的先序遍历序列，返回 false。
  • 否则，我们将 $k$ 加 $1$，然后递归搜索 $i$ 的所有子节点，如果搜索过程中发现 false，那么提前返回 false，否则搜索结束，返回 true。

在主函数中，我们调用 $dfs(nodes[0][0])$，如果返回值为 true，并且 $k = |nodes|$，那么 $nodes$ 序列是二叉树的先序遍历序列，返回 true，否则返回 false。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 是 $nodes$ 中的节点数目。

Python3

class Solution:
    def isPreorder(self, nodes: List[List[int]]) -> bool:
        def dfs(i: int) -> int:
            nonlocal k
            if i != nodes[k][0]:
                return False
            k += 1
            return all(dfs(j) for j in g[i])

        g = defaultdict(list)
        for i, p in nodes:
            g[p].append(i)
        k = 0
        return dfs(nodes[0][0]) and k == len(nodes)

Java

class Solution {
    private Map<Integer, List<Integer>> g = new HashMap<>();
    private List<List<Integer>> nodes;
    private int k;

    public boolean isPreorder(List<List<Integer>> nodes) {
        this.nodes = nodes;
        for (var node : nodes) {
            g.computeIfAbsent(node.get(1), key -> new ArrayList<>()).add(node.get(0));
        }
        return dfs(nodes.get(0).get(0)) && k == nodes.size();
    }

    private boolean dfs(int i) {
        if (i != nodes.get(k).get(0)) {
            return false;
        }
        ++k;
        for (int j : g.getOrDefault(i, List.of())) {
            if (!dfs(j)) {
                return false;
            }
        }
        return true;
    }
}

C++

class Solution {
public:
    bool isPreorder(vector<vector<int>>& nodes) {
        int k = 0;
        unordered_map<int, vector<int>> g;
        for (auto& node : nodes) {
            g[node[1]].push_back(node[0]);
        }
        function<bool(int)> dfs = [&](int i) {
            if (i != nodes[k][0]) {
                return false;
            }
            ++k;
            for (int j : g[i]) {
                if (!dfs(j)) {
                    return false;
                }
            }
            return true;
        };
        return dfs(nodes[0][0]) && k == nodes.size();
    }
};

Go

func isPreorder(nodes [][]int) bool {
	k := 0
	g := map[int][]int{}
	for _, node := range nodes {
		g[node[1]] = append(g[node[1]], node[0])
	}
	var dfs func(int) bool
	dfs = func(i int) bool {
		if i != nodes[k][0] {
			return false
		}
		k++
		for _, j := range g[i] {
			if !dfs(j) {
				return false
			}
		}
		return true
	}
	return dfs(nodes[0][0]) && k == len(nodes)
}

TypeScript

function isPreorder(nodes: number[][]): boolean {
    let k = 0;
    const g: Map<number, number[]> = new Map();
    for (const [i, p] of nodes) {
        if (!g.has(p)) {
            g.set(p, []);
        }
        g.get(p)!.push(i);
    }
    const dfs = (i: number): boolean => {
        if (i !== nodes[k][0]) {
            return false;
        }
        ++k;
        for (const j of g.get(i) ?? []) {
            if (!dfs(j)) {
                return false;
            }
        }
        return true;
    };
    return dfs(nodes[0][0]) && k === nodes.length;
}