列表

详情

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

给定一个以 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 之间，因此它不是树的前序遍历。

 

提示：

原站题解

去查看

上次编辑到这里，代码来自缓存 点击恢复默认模板
class Solution { public: bool isPreorder(vector<vector<int>>& nodes) { } };

javascript 解法, 执行用时: 192 ms, 内存消耗: 61.8 MB, 提交时间: 2023-10-17 20:11:26 

/**
 * @param {number[][]} nodes
 * @return {boolean}
 */
var isPreorder = function(nodes) {
  const stack = new Array()
  for(let i = 0; i < nodes.length; i++) {
    const [node, parent] = nodes[i]
    if(i === 0 || i > 0 && parent === nodes[i-1][0]) {
      stack.push(node)
    } else {
      let flag = false
      while(stack.length) {
        if(parent === stack.pop()) {
          flag = true
          break
        }
      }
      if(flag === false) {
        return false
      }
      stack.push(node)
    }
  }
  return true
};

java 解法, 执行用时: 46 ms, 内存消耗: 117 MB, 提交时间: 2023-10-17 20:11:05 

class Solution {
    List<List<Integer>> nodes;
    Map<Integer,List<Integer>> graph = new HashMap<>();
    int index = 0;
    public boolean isPreorder(List<List<Integer>> nodes) {
        this.nodes = nodes;
        int n = nodes.size();
        int root = -1;
        for(List<Integer> node:nodes){
            if(node.get(1)==-1) root = node.get(0);
            else{
                graph.computeIfAbsent(node.get(1),o->new ArrayList<>()).add(node.get(0));
            }
        }
        return dfs(root);
    }

    private boolean dfs(int root){
        if(nodes.get(index).get(0)!=root) return false;
        ++index;
        for(int nex:graph.getOrDefault(root,new ArrayList<>())){
            if(!dfs(nex)) return false;
        }
        return true;
    }
}

python3 解法, 执行用时: 344 ms, 内存消耗: 58.3 MB, 提交时间: 2023-10-17 20:10:13 

class Solution:
    def isPreorder(self, nodes: List[List[int]]) -> bool:
        m=-1
        for i,j in nodes:
            m=max(m,max(i,j))
        n=len(nodes)
        g=[[] for _ in range(m+1)]
        start=0
        for i,j in nodes:
            if j>=0:
                g[j].append(i)
            else:
                start=i
        check=True
        self.time=1
        
        def dfs(x,time):
            nonlocal check
            if len(g[x])==0:
                return
            for i in g[x]:
                if nodes[self.time]!=[i,x]:
                    check=False
                    return 
                else :
                    self.time+=1
                    dfs(i,self.time)
        dfs(start,self.time)
        return check

python3 解法, 执行用时: 156 ms, 内存消耗: 52.6 MB, 提交时间: 2023-10-17 20:09:57 

class Solution:
    def isPreorder(self, nodes: List[List[int]]) -> bool:
        stack=[-1]
        for i,j in nodes:
            while stack and stack[-1]!=j:
                stack.pop()
            if not stack:
                return False
            stack.append(i)
        return True

java 解法, 执行用时: 13 ms, 内存消耗: 84.1 MB, 提交时间: 2023-10-17 20:09:25 

class Solution {
    public boolean isPreorder(List<List<Integer>> nodes) {
        Deque<Integer> deque = new LinkedList<>();
        deque.push(-1);
        for (List<Integer> node : nodes) {
            int value = node.get(0);
            int parent = node.get(1);
            while (!deque.isEmpty() && deque.peek() != parent) deque.pop();
            if (deque.isEmpty()) return false;
            else deque.push(value);
        }
        return true;
    }
}

上一题

© 2024 leetcode.cn