###### tags: `提升程式設計師的面試力`
# 4.1~4.3 Tree and graphs

leetcode https://leetcode.com/problemset/all/?difficulty=Medium&listId=79h8rn6

4.1 https://wxx5433.gitbooks.io/interview-preparation/content/part_ii_leetcode_lintcode/searching/route_between_two_nodes_in_graph.html
4.2 https://desolve.medium.com/%E5%BE%9Eleetcode%E5%AD%B8%E6%BC%94%E7%AE%97%E6%B3%95-35-bst-3-b1f225f39aa3

4.3 https://wellbay.cc/thread-3931637.htm
4.3 https://algorithms.tutorialhorizon.com/in-a-binary-tree-create-linked-lists-of-all-the-nodes-at-each-depth/


## 4-1 code

<?php

class Node
{
    public $name = '';
    public array $next_node = [];
    function __construct($name)
    {
        $this->name = $name;
    }
}

class ANS
{   
    public $visit = [];

    function init(){
        $a = new Node('a');
        $b = new Node('b');
        $c = new Node('c');
        $d = new Node('d');
        $e = new Node('e');
        array_push($a->next_node,$b,$d);
        array_push($b->next_node,$c,$d);
        array_push($d->next_node,$e);
        // array_push($e->next_node,$a);//無限迴圈
        // print_r($a);
        return $a;
    }
    
    function RouteBetweenNodes(Node $graph,$s,$t){
        if($s == $t) return 'true';
        // if(in_array($graph->name,$this->visit)){//避免重複節點
        //     return 'false';
        // }
        array_push($this->visit,$graph->name);
        print_r($this->visit);
        foreach ($graph->next_node as $next_node) {
            if($graph->name == $s){
                $next_s = $next_node->name;
            }else{
                $next_s = $s;
            }
            $check = $this->RouteBetweenNodes($next_node,$next_s,$t);
            if($check == 'true') return 'true';
        }
    
        return 'false';
    }

    function theANS($s,$t){
        $ans = $this->RouteBetweenNodes($this->init(),$s,$t);
        print_r("$s 到 $t ANS: $ans");
    }

}

(new ANS())->theANS('a','b');

https://docs.google.com/presentation/d/1y9OsVD6tMt4qILmNOXKxX6C0Ok42drtUNV9FCQZb2yw/edit?usp=sharing

## 4.2 4.3

<?php

class Node
{
    public $name = 0;
    public $left = null;
    public $right = null;
    function __construct($name,$left = null,$right = null)
    {
        $this->name = $name;
        $this->left = $left;
        $this->right = $right;
    }
}

class ANS
{   
    function MinimallTree($array,$start = 0,$end = null){
        if($end === null){
            $end = count($array) - 1;
        }
        if ($end < $start) { 
            return null; 
        }
        $mid = floor(($start+$end)/2);

        $n = new Node($array[$mid]);
        $n->left = $this->MinimallTree($array,$start,$mid-1);
        $n->right = $this->MinimallTree($array,$mid+1,$end);

        return $n;
    }

    function ListOfDepths($node,$level = 0,$list = []){
        if($node === null){
            return $list;
        }
        if(isset($list[$level])){
            $list[$level][] = $node->name;
        }else{
            $list[$level] = [$node->name];
        }
        $list = $this->ListOfDepths($node->left,$level + 1,$list);
        $list = $this->ListOfDepths($node->right,$level + 1,$list);
        return $list;
    }
    
    function ListOfDepthsBYR($node,$level = 0,&$list = []){//用記憶體紀錄list
        if($node === null){
            return;
        }
        if(isset($list[$level])){
            $list[$level][] = $node->name;
        }else{
            $list[$level] = [$node->name];
        }
          $this->ListOfDepthsBYR($node->left,$level + 1,$list);
         $this->ListOfDepthsBYR($node->right,$level + 1,$list);
    }
}
$array = [1,2,3,4,5,6,7,8,9,10];

$node = (new ANS())->MinimallTree($array);//4.2
$ans = (new ANS())->ListOfDepths($node);//4.3

$qqq = [];
(new ANS())->ListOfDepthsBYR($qqq);//4.3
print_r($node);
// print_r($ans);//與qqq一樣
// print_r($qqq);