leetCode ✏Leetcode基础刷题之(150. Evaluate Reverse Polish Notation)
✏描述
使用非递归来完成二叉树的前序遍历。
✏题目实例
✏题目分析
前序遍历，先访问根结点，然后在访问左子树，最后访问右子树。可以利用栈的特点，这里我结合了队列和栈的特点来实现。先压入树，取出根节点。先把根节点值push到队列中，然后把右子树压入栈中，最后压入左子树。返回队列。当然你可以调整成你想要的实现方式。
/**
* 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) {
$res=[];
$list=[];
array_unshift($res,$root);
while(!empty($res)){
$current=array_shift($res);
if($current==null) continue;
array_push($list,$current->val);
array_unshift($res,$current->right);
array_unshift($res,$current->left);
}
return $list;
}
}
转载链接：https://leetcode.cn/
![[爱了]](/js/img/d1.gif)
![[尴尬]](/js/img/d16.gif)