devbox
繁依Fanyi0
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

算法训练day10 | php | 二叉树递归遍历， 迭代遍历，统一迭代_php二叉树遍历代码

作者：繁依Fanyi0 | 2024-03-20 15:55:35

赞

踩

php二叉树遍历代码

 先发二叉树的前、中、后序遍历的三个题目，归纳的方法在下面。

1、力扣题144. 二叉树的前序遍历

给你二叉树的根节点 root ，返回它节点值的 前序 遍历。

示例 1：

输入：root = [1,null,2,3]
输出：[1,2,3]

示例 2： 

输入：root = []
输出：[]

示例 3：

输入：root = [1]
输出：[1]

示例 4：

输入：root = [1,2]
输出：[1,2]

示例 5：

输入：root = [1,null,2]
输出：[1,2]

提示：

  • 树中节点数目在范围 [0, 100] 内
  • -100 <= Node.val <= 100

2、力扣题94. 二叉树的中序遍历

给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。

示例 1：

输入：root = [1,null,2,3]
输出：[1,3,2]

3、力扣题145. 二叉树的后序遍历

给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。

示例 1：

输入：root = [1,null,2,3]
输出：[3,2,1]

一、递归遍历

        1、前序遍历

        二叉树的前序遍历是中左右，在递归的处理逻辑中就是先处理输入的节点，再递归该节点的左节点和右节点。因为该题是返回存放遍历的值的数组，所以需设置一个全局数组用以存放二叉树的值。

        递归参数是二叉树的节点，单层递归逻辑是先将传入的二叉树节点的值放入数组，再递归左右节点，终止条件是传入的节点为null。

  1. class Solution {
  2.     private $result = [];
  3.  
  4.     /**
  5.      * @param TreeNode $root
  6.      * @return Integer[]
  7.      */
  8.     function preorderTraversal($root) {
  9.         if($root == null) 
  10.             return [];
  11.         $this->result[] = $root->val;
  12.         $this->preorderTraversal($root->left);
  13.         $this->preorderTraversal($root->right);
  14.         return $this->result;
  15.     }
  16. }

        2、后序遍历

        同上逻辑类似，只是递归左右节点和处理中节点的顺序不同。

  1. class Solution {
  2.     private $result = [];
  3.     /**
  4.      * @param TreeNode $root
  5.      * @return Integer[]
  6.      */
  7.     function postorderTraversal($root) {
  8.         if(!$root) {
  9.             return [];
  10.         }
  11.         $this->postorderTraversal($root->left);
  12.         $this->postorderTraversal($root->right);
  13.         $this->result[] = $root->val;
  14.         return $this->result;
  15.     }
  16. }

        3、中序遍历

  1. class Solution {
  2.     private $result = [];
  3.     /**
  4.      * @param TreeNode $root
  5.      * @return Integer[]
  6.      */
  7.     function inorderTraversal($root) {
  8.         if($root == null) 
  9.             return [];
  10.         $this->inorderTraversal($root->left);
  11.         $this->result[] = $root->val;
  12.         $this->inorderTraversal($root->right);
  13.         return $this->result;
  14.     }
  15. }

二、迭代遍历

       1、前序遍历

        这里的迭代遍历是使用栈来进行遍历，先将root节点放入栈中，再将root节点取出放入数组，将该root节点的右左节点放入栈中，因为是前序遍历：中左右，故放入的时候是按照右、左的顺序。然后再不断重复此过程，每从栈中取出一个节点，如果该节点的右左节点存在，都要把该节点的右左节点放入。

        这里是利用了前序遍历的特性，因为是中左右的顺序，每次在把中节点的值放入数组时，就可以顺便通过中节点来获取其左右节点了。后序遍历（左右中）也可以用与这个类似的方法。

        但是中序遍历就不可以，因为中序遍历中节点是在中间的，不好处理，无法判断哪个是中节点。

  1. class Solution {
  2.     /**
  3.      * @param TreeNode $root
  4.      * @return Integer[]
  5.      */
  6.     function preorderTraversal($root) {
  7.         $stack = new splStack();
  8.         $result = [];
  9.         $stack->push($root);
  10.         
  11.         while(!$stack->isEmpty()) {
  12.             $cur = $stack->pop();
  13.             $result[] = $cur->val;
  14.             if($cur->right) {
  15.                 $stack->push($cur->right);
  16.             }
  17.             if($cur->left) {
  18.                 $stack->push($cur->left);
  19.             }
  20.         }
  21.  
  22.         return $result;
  23.     }
  24. }
  25. 控制台

      2、后序遍历

        后序遍历的逻辑和上面前序的类似，前序是按中右左的顺序进行的，后序就要按中左右的顺序进行，最后得到的数组就是按中右左的顺序遍历的，把数组反转一下就得到了左右中也就是后序遍历了。

  1. class Solution {
  2.     /**
  3.      * @param TreeNode $root
  4.      * @return Integer[]
  5.      */
  6.     function postorderTraversal($root) {
  7.         $stack = new splStack();
  8.         $result = [];
  9.         $stack->push($root);
  10.  
  11.         while(!$stack->isEmpty()) {
  12.             $cur = $stack->pop();
  13.             $result[] = $cur->val;
  14.             if($cur->left) {
  15.                 $stack->push($cur->left);
  16.             }
  17.             if($cur->right) {
  18.                 $stack->push($cur->right);
  19.             }
  20.         }
  21.         //反转数组
  22.         $result = array_reverse($result);
  23.         return $result;
  24.     }
  25. }
  26. 控制台

        3、中序遍历

        上面已经说过了中序不能用以上的方法。中序遍历：左中右 要从左边开始遍历起，但题目又是从根节点起步，所以需要一个指针，一层层到达最左的节点，从这个节点开始处理。

        但此时指针在最底层，又如何把指针重新指向父节点呢？那么就需要在指针遍历到最左这个节点的过程中，把遍历到的节点全都入栈。在指针终于遍历到最左的节点时，把该节点出栈、放入数组，如果该节点的右节点存在，就按相同的逻辑遍历它的右节点；如果右节点也不在，就要回溯到该节点的父节点进行遍历，此时栈的顶端元素正是该节点的父节点，所以将父节点出栈处理，再重复遍历右节点、遍历父节点的过程。

        里面的单层处理过程正是左中右的顺序：

        第一层：遍历到最左（此时左节点为空），处理这个最左节点（相当于处理中节点），处理该节点的右节点。

        第二层：处理完最左节点的右节点后，指针回溯指向的最左节点的父节点也是一个中节点（此时左节点相当于这个节点的左子树，已经在上一层中遍历处理过了），再处理该节点的右节点。

  1. class Solution {
  2.     /**
  3.      * @param TreeNode $root
  4.      * @return Integer[]
  5.      */
  6.     function inorderTraversal($root) {
  7.         $stack = new splStack();
  8.         $result = [];
  9.         $cur = $root;
  10.  
  11.         while(!$stack->isEmpty() || $cur) {
  12.             if($cur) {
  13.                 $stack->push($cur);
  14.                 $cur = $cur->left;
  15.             } else {
  16.                 $cur = $stack->pop();
  17.                 $result[] = $cur->val;
  18.                 $cur = $cur->right;
  19.             }
  20.         }
  21.         return $result;
  22.     }
  23. }

三、统一遍历

        1、前序遍历

        上面的迭代遍历的方法，只适用于前后序遍历，而这个统一遍历方法是前中后序都适用的。依旧是使用栈来存放节点。每个节点会入栈两次，第一次用于获取该节点的左右节点，第二次用于将该节点的值存入数组。节点第二次入栈后，会将一个null入栈，将null放在该节点后面，用于标识。

        前中后序的区别在于，第一次把节点出栈时、再把该节点和其左右节点入栈的顺序。如果是前序遍历，就把中左右反着来，按右左中的顺序入栈（这里的中节点是第二次入栈，所以还需加一个null），其他同理。

  1. class Solution {
  2.     /**
  3.      * @param TreeNode $root
  4.      * @return Integer[]
  5.      */
  6.     function preorderTraversal($root) {
  7.         $stack = new splStack();
  8.         $result = [];
  9.         if($root) {
  10.             $stack->push($root);
  11.         }
  12.         
  13.         while(!$stack->isEmpty()) {
  14.             $cur = $stack->top();
  15.  
  16.             if($cur != null) {
  17.                 $stack->pop();
  18.  
  19.                 if($cur->right) $stack->push($cur->right);
  20.  
  21.                 if($cur->left) $stack->push($cur->left);
  22.  
  23.                 $stack->push($cur);
  24.                 $stack->push(null);
  25.             } else {
  26.                 $stack->pop();
  27.                 $temp = $stack->pop();
  28.                 $result[] = $temp->val;
  29.             }
  30.  
  31.         }
  32.  
  33.         
  34.         return $result;
  35.     }
  36. }

        2、后序遍历

        与上面的前序遍历类似，只是换了下位置

  1. class Solution {
  2.     /**
  3.      * @param TreeNode $root
  4.      * @return Integer[]
  5.      */
  6.     function postorderTraversal($root) {
  7.         $stack = new splStack();
  8.         $result = [];
  9.         if($root) $stack->push($root);
  10.  
  11.         while(!$stack->isEmpty()) {
  12.             $cur = $stack->top();
  13.             if($cur != null) {
  14.                 $stack->push(null);
  15.  
  16.                 if($cur->right) $stack->push($cur->right);
  17.  
  18.                 if($cur->left) $stack->push($cur->left);
  19.             } else {
  20.                 $stack->pop();
  21.                 $temp = $stack->pop();
  22.                 $result[] = $temp->val;
  23.             }
  24.         }
  25.         
  26.         return $result;
  27.     }
  28. }

        3、中序遍历

        同上

  1. class Solution {
  2.     /**
  3.      * @param TreeNode $root
  4.      * @return Integer[]
  5.      */
  6.     function inorderTraversal($root) {
  7.         $stack = new splStack();
  8.         $result = [];
  9.         if($root) {
  10.             $stack->push($root);
  11.         }
  12.  
  13.         while(!$stack->isEmpty()) {
  14.             $cur = $stack->top();
  15.             if($cur != null) {
  16.                 $stack->pop();
  17.                 if($cur->right) $stack->push($cur->right);
  18.  
  19.                 $stack->push($cur);
  20.                 $stack->push(null);
  21.  
  22.                 if($cur->left) $stack->push($cur->left);
  23.             } else {
  24.                 $stack->pop();
  25.                 $temp = $stack->pop();
  26.                 $result[] = $temp->val;
  27.             }
  28.         }
  29.         return $result;
  30.     }
  31. }

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/繁依Fanyi0/article/detail/274828
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号