目录

一、题目内容

二、解题思路

三、代码

一、题目内容

给定一个二叉树，返回它的 后序 遍历。

示例:

输入: [1,null,2,3]  
   1
    \
     2
    /
   3 

输出: [3,2,1]
进阶: 递归算法很简单，你可以通过迭代算法完成吗？

二、解题思路

前序遍历的迭代法需要用栈或队列来解决该问题，入栈时先右后左存储，这样出栈的都先左后右。

前序遍历：根->左->右

后序遍历：左->右->根

*后序遍历的逆：根->右->左

因此后序遍历，入栈时先左后右存储，这样出栈的都先右后左，最后翻转结果即可。

三、代码

  

   

    

     

    
    

     

      # Definition for a binary tree node.
     
    
   

    

     

    
    

     

      class TreeNode:
     
    
   

    

     

    
    

     
 def __init__(self, x):
     
    
   

    

     

    
    

     

       self.val = x
     
    
   

    

     

    
    

     

       self.left = None
     
    
   

    

     

    
    

     

       self.right = None
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      class Solution:
     
    
   

    

     

    
    

     
 def preorderTraversal(self, root: TreeNode) -> list:
     
    
   

    

     

    
    

     
 if root is None:
     
    
   

    

     

    
    

     
 return []
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

       res = []
     
    
   

    

     

    
    

     

       stack = [root]
     
    
   

    

     

    
    

     
 while stack:
     
    
   

    

     

    
    

     

       cur = stack.pop()
     
    
   

    

     

    
    

     

       res.append(cur.val)
     
    
   

    

     

    
    

     
 if cur.left:
     
    
   

    

     

    
    

     

       stack.append(cur.left)
     
    
   

    

     

    
    

     
 if cur.right:
     
    
   

    

     

    
    

     

       stack.append(cur.right)
     
    
   

    

     

    
    

     
 return res[::-1]
     
    
  
 

文章来源: nickhuang1996.blog.csdn.net，作者：悲恋花丶无心之人，版权归原作者所有，如需转载，请联系作者。

原文链接：nickhuang1996.blog.csdn.net/article/details/108713557