144.md

✏️Leetcode基础刷题之(150. Evaluate Reverse Polish Notation)

2019-05-03 吴亲库里 库里的深夜食堂

---

✏️描述

使用非递归来完成二叉树的前序遍历。

✏️题目实例

​

✏️题目分析

前序遍历，先访问根结点，然后在访问左子树，最后访问右子树。可以利用栈的特点，这里我结合了队列和栈的特点来实现。先压入树，取出根节点。先把根节点值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;
             
         }
     }

---

联系

​