生成tree

 <?php
 $arr = array(
     array('id' => 1, 'pid' => -1, 'name' => 'test1', ),
     array('id' => 2, 'pid' => -1, 'name' => 'test2', ),
     array('id' => 3, 'pid' => -1, 'name' => 'test3', ),
     array('id' => 4, 'pid' => -1, 'name' => 'test4', ),
     array('id' => 5, 'pid' =>  1, 'name' => 'test5', ),
     array('id' => 6, 'pid' =>  2, 'name' => 'test6', ),
     array('id' => 7, 'pid' =>  3, 'name' => 'test7', ),
     array('id' => 8, 'pid' =>  4, 'name' => 'test8', ),
     array('id' => 9, 'pid' =>  7, 'name' => 'test9', ),
     array('id' => 10, 'pid' => -1, 'name' => 'test10', ),
 );
 $maps = array();
 foreach ($arr as $index => $item) {
     $maps[$item['id']] = &$arr[$index];
 }
 $returnList = array();
 foreach ($arr as $index => $item) {
     if ($item['pid'] !== -1) {
         if (!isset($maps[$item['pid']]['child'])) {
             $maps[$item['pid']]['child'] = array();
         }       
         $maps[$item['pid']]['child'][] = &$maps[$item['id']];
     } else {
         $returnList[] = &$maps[$item['id']];
     }
 }
 var_dump($returnList);exit;
 echo json_encode($returnList);

二叉树

https://segmentfault.com/a/1190000009370316
https://blog.csdn.net/baidu_30000217/article/details/52953127

class TreeNode {
    public $val = null;
    public $left = null;
    public $right = null;

    function __construct($value) {
        $this->val = $value;
    }
}

先序遍历

//二叉树先序遍历  递归版
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        preorderHelper(root, res);
        return res;
    }

    public void preorderHelper(TreeNode root, List<Integer> res) {
        if (root == null) {
            return;
        }

        res.add(root.val);
        if (root.left != null) {
            preorderHelper(root.left, res);
        }

        if (root.right != null) {
            preorderHelper(root.right, res);
        }
    }

    //二叉树先序遍历  非递归版
    public List<Integer> preorderTraversal2(TreeNode root) {
        LinkedList<TreeNode> stack = new LinkedList<TreeNode>();
        List<Integer> res = new ArrayList<Integer>();
        if (root == null) {
            return res;
        }
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode tmp = stack.poll();
            res.add(tmp.val);
            if (tmp.right != null) {
                stack.push(tmp.right);
            }

            if (tmp.left != null) {
                stack.push(tmp.left);
            }
        }
        return res;
    }

后序遍历

//二叉树后序遍历 递归版
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        postOrderHelper(root, res);
        return res;
    }

    public void postOrderHelper(TreeNode root, List<Integer> res) {
        if (root == null) {
            return;
        }
        if (root.left != null) {
            postOrderHelper(root.left, res);
        }

        if (root.right != null) {
            postOrderHelper(root.right, res);
        }
        res.add(root.val);
    }

    //二叉树后序遍历 非递归版
    public List<Integer> postorderTraversal2(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        if (root == null) {
            return res;
        }
        TreeNode head = root;
        LinkedList<TreeNode> stack = new LinkedList<TreeNode>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode tmp = stack.peek();
            if ((tmp.left == null && tmp.right == null)
                    || tmp.left == head
                    || tmp.right == head
            ) {
                res.add(tmp.val);
                stack.poll();
                head = tmp;
            } else {
                if (tmp.right != null) {
                    stack.push(tmp.right);
                }
                if (tmp.left != null) {
                    stack.push(tmp.left);
                }
            }
        }
        return res;
    }

中序遍历

左根右

/**
     * @param TreeNode $root
     * @return Integer[]
     * @brief 二叉树中序遍历(递归) 左->根->右
     */
    function inorderTraversal($root) {
        if (!is_null($root)) {
            $func = __FUNCTION__;
            $this->$func($root->left);
            echo $root->val . ",";
            $this->$func($root->right);
        }
    }

    /**
     * inorder
     * @param TreeNode $root
     * @return void
     * @brief 中序遍历非递归版本
     * 1.循环将左子树插入栈
     * 2.pop栈，打印当前节点val
     * 3.将pop栈出来的节点循环第1个步骤
     */
    function inorder($root) {
        if (!$root) {
            return;
        }
        $stack = new splstack;
        while ($root || !$stack->isEmpty()) {

            //循环将左子树push入stack
            while ($root) {
                $stack->push($root);
                $root = $root->left;
            }
            //pop stack，打印当前val
            $root = $stack->pop();
            echo $root->val . ",";
            //继续针对右子数循环上述
            $root = $root->right;
        }
    }

广度优先遍历

    /**
     * leverOrder
     * @param TreeNode $root
     * @return void
     * @brief 广度优先遍历
     */
    function leverOrder($root) {
        $queue = new splqueue();
        $queue->enqueue($root);
        while (!$queue->isEmpty()) {
            $root = $queue->dequeue();
            echo $root->val . ",";

            if ($root->left) {
                $queue->enqueue($root->left);
            }

            if ($queue->right) {
                $queue->enqueue($root->right);
            }
        }
    }

树的深度

/**
     * getDepth
     * @param TreeNode $root
     * @return int
     * @brief 获取树的深度
     */
    function getDepth($root) {
        if (!$root) {
            return 0;
        }
        //叶子节点
        if (!$root->left && !$root->right) {
            return 1;
        }
        $leftDepth  = $this->getDepth($root->left);
        $rightDepth = $this->getDepth($root->right);
        $maxDepth   = $rightDepth >= $leftDepth ? $rightDepth : $leftDepth;
        $depth      = $maxDepth + 1;
        return $depth;
    }

判断一个树是不是BST，二叉搜索树

方法一：中规中矩，没毛病，中序遍历，然后判断结论是否递增

    /**
     * @param TreeNode $root
     * @return Boolean
     * @bierf 判断一个树是不是二叉搜索树 BST
     * 方法1：中序遍历二叉树，判断结果是不是递增
     */
    function isValidBST1($root) {
        $outArr = $this->inorderTraversal($root);
        $tmp    = 0;
        foreach ($outArr as $item) {
            if ($tmp <= $item) {
                $tmp = $item;
            } else {
                return false;
            }
        }
        return true;
    }

方法二：
利用搜索二叉树的特性，左<中<右
有一个很有意思的例子，请拿这个例子来看看下面的算法对不对

image.png

  /**
     * @param TreeNode $root
     * @return Boolean
     * @bierf 判断一个树是不是二叉搜索树 BST
     * 方法2：判断左子树和右子树与根节点的大小关系
     */
    function isValidBST2($root) {
        return $this->valiadBST($root, PHP_INT_MIN, PHP_INT_MAX);
    }

    /**
     * valiadBST
     * @param TreeNode $root
     * @param $min
     * @param $max
     * @return bool
     */
    function valiadBST($root, $min, $max) {
        if (!$root) {
            return true;
        }

        if (($root->val <= $min) || ($root->val >= $max)) {
            return false;
        }

        $flag1 = $this->valiadBST($root->left, $min, $root->val);
        $flag2 = $this->valiadBST($root->right, $root->val, $max);
        return $flag1 && $flag2;
    }

二叉排序数的生成

• 给出一个整数n，生成（1，n）的所有可能的二叉排序树(BST)
  题目地址：https://leetcode.com/problems/unique-binary-search-trees-ii/

利用二叉搜索数的特性，左子树的所有值小于根节点，右子树的所有值大于根节点，所以以i为根节点，左子树为(1,i-1)，右子树为(i+1,n),
参考链接
参考链接2

    /**
     * generateBST
     * @param $n
     * @return void
     */
    function generateBST($n) {
        $r = $this->genHelper(1, $n);
        return $r;
    }

/**
     * genHelper
     * @param $left
     * @param $right
     * @return $res
     */
    function genHelper($left, $right) {
        $res = array();
        if ($left > $right) {
            $res[] = null;
            return $res;
        }

        for ($i = $left; $i <= $right; $i++) {
            $leftList  = $this->genHelper($left, $i - 1);
            $rightList = $this->genHelper($i + 1, $right);
            for ($j = 0; $j < count($leftList); $j++) {
                for ($k = 0; $k < count($rightList); $k++) {
                    $root        = new TreeNode($i);
                    $root->left  = $leftList[$j];
                    $root->right = $rightList[$k];
                    $res[]       = $root;
                }
            }
        }

        return $res;
    }

中序遍历和先序遍历生成搜索二叉树

https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/submissions/
解析：先序遍历 preorder 根左右，中序遍历inorder左根右，通过先序遍历找到根节点的值，通过这个值在中序遍历中分别找到左子树和右子树的order，然后继续基于左子树和右子树的preorder 和inorder迭代
划重点：这个二叉树中没有重复的值，这是这个题目的先决条件，否则在中序遍历的array中查找根节点时，会出问题

 /**
     * @param Integer[] $preorder
     * @param Integer[] $inorder
     * @return TreeNode
     * @brief 通过先序遍历和中序遍历还原一个BST
     */
    function buildTree($preorder, $inorder) {
        if (!$preorder || !$inorder) {
            return null;
        }

        return $this->buildHelper($preorder, 0, count($preorder) - 1, $inorder, 0, count($inorder) - 1);
    }


    /**
     * buildHelper
     * @param TreeNode $preorder
     * @param TreeNode $preL
     * @param $preR
     * @param $inorder
     * @param $inL
     * @param $inR
     * @return TreeNode
     */
    function buildHelper($preorder, $preL, $preR, $inorder, $inL, $inR) {

        if ($preL > $preR || $inL > $inR) {
            return null;
        }
        $root        = new TreeNode($preorder[$preL]);//先序遍历的第一个为root
        $index       = array_search($root->val, $inorder);//中序遍历的index

        //对于中序遍历 $index-$inL 就是左子树的长度，所以此时的$preR = $preL + $index - $inL
        $root->left  = $this->buildHelper($preorder, $preL + 1, $index - $inL + $preL, $inorder, $inL, $index - 1);

        //同理，$index-$inL为左子树的长度 所以右子树的起始位置是$preL = $preL + $index-$inL + 1
        $root->right = $this->buildHelper($preorder, $preL + $index - $inL + 1, $preR, $inorder, $index + 1, $inR);
        return $root;
    }

中序遍历和后序遍历还原BST

https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/submissions/
类似先序遍历和中序遍历还原BST

 /**
     * buildTreeS
     * @param $inorder
     * @param $postorder
     * @return null|TreeNode
     * @brief 通过后序遍历和中序遍历还原一个BST
     */
    function buildTreeS($inorder, $postorder) {
        if (!$inorder || !$postorder) {
            return null;
        }

        return $this->buildSHelper($postorder, 0, count($postorder) - 1, $inorder, 0, count($inorder) - 1);

    }

    /**
     * buildSHelper
     * @param $postorder
     * @param $pL
     * @param $pR
     * @param $inorder
     * @param $inL
     * @param $inR
     * @return null|TreeNode
     */
    function buildSHelper($postorder, $pL, $pR, $inorder, $inL, $inR) {
        if ($pL > $pR || $inL > $inR) {
            return null;
        }
        $root  = new TreeNode($postorder[$pR]);//后续遍历的最后一个一定是根节点
        $index = array_search($postorder[$pR], $inorder);//找到根节点在中序遍历的位置

        $root->left  = $this->buildSHelper($postorder, $pL, $pL + $index - $inL - 1, $inorder, $inL, $index - 1);
        $root->right = $this->buildSHelper($postorder, $pL + $index - $inL, $pR-1, $inorder, $index + 1, $inR);
        return $root;
    }

数组生成BST

已排好序的数组，生成BST:https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/

  /**
     * @param Integer[] $nums
     * @return TreeNode
     * @brief 已排好序的array，生成BST，
     */
    function sortedArrayToBST($nums) {
        return $this->sortArrHelper($nums, 0, count($nums) - 1);
    }

    /**
     * sortArrHelper
     * @param $arr
     * @param $left
     * @param $right
     * @return null|TreeNode
     */
    function sortArrHelper($arr, $left, $right) {
        if ($left > $right) {
            return null;
        }
        $mid         = intval(($left + $right) / 2);
        $midVal      = $arr[$mid];
        $root        = new TreeNode($midVal);
        $root->left  = $this->sortArrHelper($arr, $left, $mid - 1);
        $root->right = $this->sortArrHelper($arr, $mid + 1, $right);
        return $root;
    }

基于深度优先遍历从下到上输出BST

https://leetcode.com/problems/binary-tree-level-order-traversal-ii/submissions/

image.png

• splqueue 的dequeue是从队尾弹出，pop是从队头弹出（pop是保证先进先出）

/**
     * levelOrderBottom
     * @param TreeNode $root
     * @return void
     *
     */
    function levelOrderBottom($root) {
        if (!$root) {
            return [];
        }
        $queue = new splqueue();
        $queue->push($root);
        $res = array();
        while (!$queue->isEmpty()) {
            $count  = $queue->count();
            $tmpArr = [];
            for ($i = 0; $i < $count; $i++) {
                $root = $queue->dequeue();

                $tmpArr[] = $root->val;

                if ($root->left) {
                    $queue->push($root->left);
                }

                if ($root->right) {
                    $queue->push($root->right);
                }
            }
            array_unshift($res, $tmpArr);
        }
        return $res;
    }

判断一个二叉树是不是平衡二叉树

    /**
     * @param TreeNode $root
     * @return Boolean
     */
    function isBalanced($root) {
        if (!$root) {
            return true;
        }
        $leftDepth  = $this->getDepth($root->left);
        $rightDepth = $this->getDepth($root->right);
        if (abs($leftDepth - $rightDepth) > 1) {
            return false;
        }

        return $this->isBalanced($root->left) && $this->isBalanced($root->right);

    }

Path Sum

题目连接：https://leetcode.com/problems/path-sum-ii/
给定一个二叉树和一个int数值，找出所有的根节点到叶子节点的组合，指的根节点到叶子节点的路径上的和等于该int值

---

深度优先遍历树，将每次遍历的val存入一个一维数组res,当发现遍历到某个叶子节点并且刚好节点值的和为sum，则此res就是一个解集，存入最终结果集arr二维数组。
如果发现该节点对应子树没有能找到结果集，则要将节点pop出res集合

    /**
     * @param TreeNode $root
     * @param Integer $sum
     * @return Integer[][]
     */
    function pathSum($root, $sum) {
        $res = [];
        $arr = [];
        $this->pathSumHelper($root,$sum,$res,$arr);
        return $arr;
    }

    /**
     * pathSumHelper
     * @param TreeNode $root
     * @param $sum
     * @param $res
     * @param $arr
     * @return void
     */
    function pathSumHelper($root, $sum, &$res, &$arr){
        if (!$root) {
            return;
        }
        $res[] = $root->val;
        $sum   = $sum - $root->val;

        if (!$sum && !$root->right && !$root->left) {
            $arr[] = $res;
        }

        $this->pathSumHelper($root->left, $sum, $res, $arr);
        $this->pathSumHelper($root->right, $sum, $res, $arr);
        array_pop($res);//精髓pop,
    }

测试case:

$tree1        = new TreeNode(5);
$tree2       = new TreeNode(4);
$tree3       = new TreeNode(8);
$tree4       = new TreeNode(11);
$tree5       = new TreeNode(13);
$tree6       = new TreeNode(4);
$tree7       = new TreeNode(7);
$tree8       = new TreeNode(2);
$tree9       = new TreeNode(5);
$tree10       = new TreeNode(1);
$tree1->left = $tree2;
$tree1->right = $tree3;
$tree2->left = $tree4;
$tree4->left = $tree7;
$tree4->right = $tree8;
$tree3->left = $tree5;
$tree3->right = $tree6;
$tree6->left = $tree9;
$tree6->right = $tree10;
$so          = new Solution();
$r           = $so->pathSum($tree1,22);
var_dump($r);
exit;

Has Path Sum

path sum的简化版，只需要找出是否存在路径和等于sum，不用列举具体路径

/**
     * hasPathSum
     * @param $root
     * @param $sum
     * @return bool
     */
    function hasPathSum($root, $sum) {

        if(!$root){
            return false;
        }
        if ($sum == $root->val && !$root->left && !$root->right) {
            return true;
        }
        $flagL = $this->hasPathSum($root->left, $sum - $root->val);
        $flagR = $this->hasPathSum($root->right, $sum - $root->val);
        return $flagL || $flagR;
    }

Flatten Binary Tree to Linked List

https://leetcode.com/problems/flatten-binary-tree-to-linked-list/
将一个二叉树转化为链表形式

 /**
     * @param TreeNode $root
     * @return NULL
     * @brief https://leetcode.com/problems/flatten-binary-tree-to-linked-list/
     */
    function flatten($root) {
        $res = new TreeNode(PHP_INT_MAX);
        $this->flattenHelper($root, $res, $out);
        $root = $out;
        return $out;
    }

    /**
     * flattenHelper
     * @param TreeNode $root
     * @param TreeNode $res
     * @return void
     */
    function flattenHelper($root, &$res, &$out) {

        if (!$root) {
            return;
        }
        $newRoot = new TreeNode($root->val);
        if ($res->val == PHP_INT_MAX) {
            $res = $newRoot;
            $out = $res;
        } else {
            $res->right = $newRoot;
            $res        = $res->right;
        }

        $this->flattenHelper($root->left, $res, $out);
        $this->flattenHelper($root->right, $res, $out);
        return;
    }

数组生成二叉树

根据数组，生成二叉树
例如：[7, -10, 2, -4, 3, -8, null, null, null, null, -1, 11]生成

image.png

    /**
     * createTree2
     * @param TreeNode $root
     * @param $arr
     * @param $len
     * @param $index
     * @return void
     */
    function createTree2(&$root, $arr, $len, $index) {
        if ($index >= $len) {
            return;
        }
        $val  = $arr[$index];
        $root = new TreeNode($val);
        $this->createTree2($root->left,$arr,$len,2 * $index + 1);
        $this->createTree2($root->right,$arr,$len,2 * $index + 2);
    }

最小公共父节点

https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/
给定一个二叉树root，同时给定root的两个子树p和q，求p和q的最小公共父节点

递归大法，如果当前节点不等于p或者q，那么p或者q一定在当前节点的子节点中，有三种情况
1.p,q都位于左子树，这里有两种情况，一种情况是left会返回p和q中较高的那个位置，而right会返回空，所以我们最终返回非空的left即可，这就是题目中的例子2的情况。还有一种情况是会返回p和q的最小父结点，就是说当前结点的左子树中的某个结点才是p和q的最小父结点，会被返回。
2.p，q都位于右子树，同样这里有两种情况，一种情况是right会返回p和q中较高的那个位置，而left会返回空，所以我们最终返回非空的right即可，还有一种情况是会返回p和q的最小父结点，就是说当前结点的右子树中的某个结点才是p和q的最小父结点，会被返回
3.p，q分别位于左子树和右子树，这种情况，分别对左子树和右子树调用递归，一定会返回p或q的公共节点

 /**
     * lowestCommonAncestor
     * @param TreeNode $root
     * @param TreeNode $p
     * @param TreeNode $q
     * @return void
     */
    function lowestCommonAncestor($root, $p, $q) {
        if (!$root || $p == $root || $q == $root) {
            return $root;
        }
        $left  = $this->lowestCommonAncestor($root->left, $p, $q);
        $right = $this->lowestCommonAncestor($root->right, $p, $q);
        if ($left && $right) {
            return $root;
        }
        return $left ? $left : $right;
    }