Tree
2017-10-17 本文已影响0人
瞬铭
生成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;
}
