LeetCode - 2196

2026年1月1日

LeetCode 2196

解法

分析 descriptions:

節點值唯一，可作為 key 使用
可使用 Hash Table 建立節點關係並取得對應節點

分析數值限制:

max(parenti, childi) <= 10^5
descriptions.length <= 10^4

權衡效能:

在實務經驗中，當值域大小相對於資料筆數為十幾倍以內時，可用 Array 取代 Hash Table 以提升效能

程式碼

java

public TreeNode createBinaryTree(int[][] descriptions) {
  int maxVal = 0;
  for (int[] d : descriptions) {
    maxVal = Math.max(maxVal, Math.max(d[0], d[1]));
  }
  TreeNode[] nodes = new TreeNode[maxVal + 1];
  boolean[] isChild = new boolean[maxVal + 1];
  for (int[] d : descriptions) {
    int parentVal = d[0];
    int childVal = d[1];
    boolean isLeft = d[2] == 1;
    if (nodes[parentVal] == null) {
      nodes[parentVal] = new TreeNode(parentVal);
    }
    if (nodes[childVal] == null) {
      nodes[childVal] = new TreeNode(childVal);
    }
    if (isLeft) {
      nodes[parentVal].left = nodes[childVal];
    } else {
      nodes[parentVal].right = nodes[childVal];
    }
    isChild[childVal] = true;
  }
  for (int i = 1; i <= maxVal; i++) {
    if (nodes[i] != null && !isChild[i]) {
      return nodes[i];
    }
  }
  return null;
}