leetCode Leetcode基础刷题之PHP解析(94. Binary Tree Inorder Traversal)
.
✏题目描述
给定一个二叉树，返回其中序遍历：左->根->右,当然这道题要求的是用非递归来完成。前序后序在之前的一篇文章有非递归实现，特意留下中序，用递归和非递归一起实现。
✏题目实例
✏题目分析
对于树这种题目，我们一般都会利用栈和队列的特性来完成，递归的话定义一个辅助函数，我这里存储树的时候利用栈后进先出的特点，最后的值利用队列的特性。
/**
* 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) {
$res=[];
$this->helper($root,$res);
return $res;
}
function helper($root,&$res){
if($root !=null){
if($root->left !=null){
$this->helper($root->left,$res);
}
array_push($res,$root->val);
if($root->right !=null){
$this->helper($root->right,$res);
}
}
}
}
✏迭代
如果是迭代的话，套路还是一样的。先将根节点压入栈中，然后将其所有的左子节点依次压入栈中，取出栈顶元素，保存至队列中，再把指针指向他的右子节点上，如果存在右子节点，循环又把右子节点的左子节点压入栈中，保证了中序遍历的顺序。
/**
* @param TreeNode $root
* @return Integer[]
*/
function inorderTraversal($root) {
$res=[];
$data=[];
while(!empty($res) || $root !=null){
while($root !=null){
array_unshift($res,$root);
$root=$root->left;
}
$root=array_shift($res);
array_push($data,$root->val);
$root=$root->right;
}
return $data;
}
转载链接：https://leetcode.cn/
![[爱了]](/js/img/d1.gif)
![[尴尬]](/js/img/d16.gif)