计算二叉树深度
输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。
例如：
给定二叉树 [3,9,20,null,null,15,7]，
3
/ \
9 20
/ \
15 7
返回它的最大深度 3 。
提示：
节点总数 <= 10000
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/er-cha-shu-de-shen-du-lcof
直接递归左边，再递归右边，比较两个深度的最大值即可，最终需要加一，因为根也算是一个深度。 php 代码
/**
* Definition for a binary tree node.
* class TreeNode {
* public $val = null;
* public $left = null;
* public $right = null;
* function __construct($value) { $this->val = $value; }
* }
*/
class Solution {
/**
* @param TreeNode $root
* @return Integer
*/
function maxDepth($root) {
if ($root == null) {
return 0;
}
$leftDepth = $this->maxDepth($root->left);
$rightDepth = $this->maxDepth($root->right);
return max($leftDepth, $rightDepth) + 1;
}
}
二叉树的前序遍历
给定一个二叉树，返回它的 前序 遍历。
示例:
输入: [1,null,2,3]
1
\
2
/
3
输出: [1,2,3]
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/binary-tree-preorder-traversal
递归实现太简单了，此次用迭代实现，借助 array_push 不断将数据插入数组尾部，然后优先判断右边的数据，不为空则压入栈，先进后出，则相当于还是先读取左子树数据（先压左边数据的话，可以使用队列，效果一样）。
PHP 代码：
/**
* Definition for a binary tree node.
* class TreeNode {
* public $val = null;
* public $left = null;
* public $right = null;
* function __construct($value) { $this->val = $value; }
* }
*/
class Solution {
/**
* @param TreeNode $root
* @return Integer[]
*/
function preorderTraversal($root) {
$s = new SplStack();
$s->push($root);
$result = [];
while(!$s->isEmpty()) {
$data = $s->pop();
array_push($result, $data->val);
if ($data->right != null) {
$s->push($data->right);
}
if ($data->left != null) {
$s->push($data->left);
}
}
return $result;
}
}
二叉树的后序遍历
给定一个二叉树，返回它的 后序 遍历。
示例:
输入: [1,null,2,3]
1
\
2
/
3
输出: [3,2,1]
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/binary-tree-postorder-traversal
递归实现太简单了，此次用迭代实现，借助 array_unshift 不断将数据插入数组头部，然后优先判断左边的数据，不为空则压入栈，先进后出，则相当于还是先读取右子树数据。
PHP 实现
/**
* Definition for a binary tree node.
* class TreeNode {
* public $val = null;
* public $left = null;
* public $right = null;
* function __construct($value) { $this->val = $value; }
* }
*/
class Solution {
/**
* @param TreeNode $root
* @return Integer[]
*/
function postorderTraversal($root) {
$s = new SplStack();
$s->push($root);
$result = [];
while(!$s->isEmpty()) {
$data = $s->pop();
array_unshift($result, $data->val);
if ($data->left != null) {
$s->push($data->left);
}
if ($data->right != null) {
$s->push($data->right);
}
}
return $result;
}
}
二叉树的中序遍历
给定一个二叉树，返回它的中序遍历结果。
示例:
输入: [1,null,2,3]
1
\
2
/
3
输出: [1,3,2]
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/binary-tree-inorder-traversal
主要先向左走到头，弹出栈顶元素，向右跳一步，再重复上述步骤，顺序是左中右的处理。
PHP 实现：
/**
* Definition for a binary tree node.
* class TreeNode {
* public $val = null;
* public $left = null;
* public $right = null;
* function __construct($value) { $this->val = $value; }
* }
*/
class Solution {
/**
* @param TreeNode $root
* @return Integer[]
*/
function inorderTraversal($root) {
$stack = new SplStack();
$result = [];
$pNode = $root;
while ($pNode !== null || !$stack->isEmpty()) {
if ($pNode !== null) {
$stack->push($pNode);
$pNode = $pNode->left;
} else {
$node = $stack->pop();
$result[] = $node->val;
$pNode = $node->right;
}
}
return $result;
}
}
