<?php

$data = array(
  135 => array(
    150 => array(
      151 => array(
        1 => array(),
        153 => array(),
      ),
      1 => array(
        1 => array(),
        2 => array(),
      ),
    ),
    1 => array(
      1 => array(
        1 => array(),
        2 => array(),
      ),
      2 => array(
        1 => array(),
        2 => array(),
      ),
    ),
  ),
);

/**
 * traverse array and
 * add parent key to children key
 * 
 * @param array $a (return)
 * @param int $p (optional) parent key 
 */
function changeKeys(array &$a, $p = null)
{
    static $f = __FUNCTION__;
    
    foreach($a as $k => &$v)
    {
        # test if already processed
        if (is_string($k))
            return;

        # traverse children if children exists
        if ($v)
            $f($v, $k);        

        # rename key if parent exists
        if ($p)
        {
            $a["$k|$p"] = &$v;            
            unset($a[$k]);
        }
    }
}

changeKeys($data);

print_r($data);

Array
(
    [135] => Array
        (
            [150|135] => Array
                (
                    [151|150] => Array
                        (
                            [1|151] => Array
                                (
                                )

                            [153|151] => Array
                                (
                                )

                        )

                    [1|150] => Array
                        (
                            [1|1] => Array
                                (
                                )

                            [2|1] => Array
                                (
                                )

                        )

                )

            [1|135] => Array
                (
                    [1|1] => Array
                        (
                            [1|1] => Array
                                (
                                )

                            [2|1] => Array
                                (
                                )

                        )

                    [2|1] => Array
                        (
                            [1|2] => Array
                                (
                                )

                            [2|2] => Array
                                (
                                )

                        )

                )

        )

)