145.二叉树的后序遍历.md

题目链接

https://leetcode-cn.com/problems/binary-tree-postorder-traversal/submissions/

解法

1.递归
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res  = new ArrayList<>();
        helper(root,res);
        return res;
    }
    public void helper(TreeNode node,List<Integer> list){
        if(node == null) return ;
        if(node.left != null)   helper(node.left,list);
        if(node.right != null)  helper(node.right,list);
        list.add(node.val);
    }
}
2.非递归
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if(root == null)    return res;
        Stack<TreeNode> stack = new Stack<>();
        //表示刚刚访问的节点
        TreeNode flag = null;
        TreeNode p = root;
        while(p != null || !stack.isEmpty()){
            if(p != null){
                //一直走到最左边
                stack.push(p);
                p = p.left;
            }
            else{
                //已经到了最左最下
                //找到栈顶节点
                p = stack.peek();
                //如果右子树存在,并且没有被访问过
                if(p.right != null && p.right != flag){
                    p = p.right;
                    stack.push(p);
                    p = p.left;
                }
                else{
                    //没有右子树,或者已经被访问过,直接访问当前节点
                    p = stack.pop();
                    res.add(p.val);
                    //记录最近访问过的节点
                    flag = p;
                    //节点访问完毕重置p
                    p = null;
                }
                

            }
        }
        return res;
    }
  
}

总结:

这个后序遍历的非递归解法我自己是想不到的,里面使用了一个flag变量来保存之前访问过的节点,这个很难想到的,想不到就只能记住它了,过几天回来看。

Copyright: 采用 知识共享署名4.0 国际许可协议进行许可

Links: https://hadoo666.top/archives/145二叉树的后序遍历md