0


Leetscode.comからのこの問題と混同していますが、このアルゴリズムはトップダウンですか、それともボトムアップですか？

public static TreeNode addToTree(int arr[], int start, int end){ 
  if (end < start) {
    return null;
  }
 int mid = (start + end) / 2;
 TreeNode n = new TreeNode(arr[mid]); 
 n.left = addToTree(arr, start, mid - 1); 
 n.right = addToTree(arr, mid + 1, end); 
 return n;
}

ありがとうございました

4

1 に答える 1

1

それがトップダウンのアプローチです。このアルゴリズムは中間要素をノードに配置し、次に左右のサブツリーを構築します。したがって、最上位ノードが最初に作成され、次にツリーが下方向に成長します。

ボトムアップのアプローチでは、左右のサブツリーが最初に作成され、次にそれらが親に追加されます。次のようになります。

public static TreeNode addToTree(int arr[], int start, int end){ 
    if (end < start) {
        return null;
    }

    int mid = (start + end) / 2; 
    TreeNode left = addToTree(arr, start, mid - 1); 
    TreeNode right = addToTree(arr, mid + 1, end); 
    TreeNode n = new TreeNode(arr[mid]);
    n.left = left;
    n.right = right;
    return n;
}

このアプローチでは、ツリーの一番下のノードが最初に作成され、ツリーは上向きに構築されます。

于 2012-07-18T04:44:30.020 に答える