Leetcode刷题100天—145. 二叉树的后序遍历(二叉树)—day08

骑猪看日落 2022-09-10 03:16 101阅读 0赞

前言：

> 作者：神的孩子在歌唱
> 
> 大家好，我叫运智

![image-20210902105211837][]

#### [145. 二叉树的后序遍历][145.] ####

难度简单661收藏分享切换为英文接收动态反馈

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

**示例:**

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

**进阶:** 递归算法很简单，你可以通过迭代算法完成吗？

package 二叉树;
    
    import java.util.ArrayList;
    import java.util.Deque;
    import java.util.LinkedList;
    import java.util.List;
    
    /* * 4 * https://leetcode-cn.com/problems/binary-tree-postorder-traversal/ （递归+迭代） */
    public class _145_二叉树的后序遍历 { 
    // 后序+递归
    	public List<Integer> postorderTraversal(TreeNode root) { 
    // 后序:后序左子树,后序右子树,根节点
    		List<Integer> res=new ArrayList<Integer>();
    
    		preorder(res, root);
    		return res;
    	}
    	public void preorder(List<Integer> res,TreeNode root) { 
    		
    // 终止循环条件
    		if (root==null) { 
    			return;
    		}
    		preorder(res, root.left);
    		preorder(res, root.right);
    		res.add(root.val);	   
    	}
    // 后序+迭代
    	public List<Integer> postorderTraversal2(TreeNode root) { 
    // 后序:后序左子树,后序右子树,根节点
    		List<Integer> res=new ArrayList<Integer>();
    		if (root==null) { 
    			return res;
    		}
    // 创建栈用于存放子树
    		Deque<TreeNode> stack=new LinkedList<TreeNode>();
    // 创建指针
    		TreeNode node=root;
    	    TreeNode prev = null;
    // 如果到达叶子节点或者栈为空就终止循环
    		while(node!=null||!stack.isEmpty()) { 
    //遍历左子树
    			while(node!=null) { 
    				stack.push(node);
    				node=node.left;
    			}
    // 弹出栈
    			node=stack.pop();
    // 遍历右子树,如果该节点右右子树就入栈
    			if(node.right==null|| node.right== prev) { //node.right== prev是防止出现死循环
                    // stack.push(node);
                    res.add(node.val);
                    prev = node;
                    node = null;
    				
    			}else { 
                    stack.push(node);
    				node=node.right;
    				
    			}
    		}
    		return res;
    	}
    }

> 本人csdn博客：https://blog.csdn.net/weixin\_46654114
> 
> 转载说明：跟我说明，务必注明来源，附带本人博客连接。

[image-20210902105211837]: /images/20220829/4b92c2f83ea049939dc6e5bfab755848.png
[145.]: https://leetcode-cn.com/problems/binary-tree-postorder-traversal/