二叉树的后序遍历

145. 二叉树的后序遍历

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

代码

class Solution {
    List<Integer> list = new ArrayList<>();
    public List<Integer> postorderTraversal(TreeNode root) {
        // postorder01(root);
        postorder02(root);
        // postorder03(root);
        return list;
    }
    
    //递归
    public void postorder01(TreeNode root){
        if(root==null) return;
        postorder01(root.left);
        postorder01(root.right);
        list.add(root.val);
    }
    

    //迭代
    public void postorder02(TreeNode root){
        if(root==null) return;
        Stack<TreeNode> st = new Stack<>();
        TreeNode pre = null; //标记上一个访问节点
        while(root!=null||!st.isEmpty()){
            while(root!=null){
                st.push(root);
                root = root.left;
            }
            root = st.peek(); //查看栈顶节点
            if(root.right != null && root.right != pre){ //若栈顶元素右节点为空，或右节点已被访问才访问该节点
                root = root.right;
            }else{//否则不访问该结点，指向右节点
                root = st.pop();
                list.add(root.val);
                pre = root; //pre指向该访问的结点
                root = null;
            }
        }
    }

    //迭代标记法
    public void postorder03(TreeNode root){
        if(root==null) return;
        Stack<TreeNode> st = new Stack<>();
        st.push(root);
        while(!st.isEmpty()){
            TreeNode node = st.pop();
            if(node!=null){
                st.push(node);//中
                st.push(null);//标记
                if(node.right!=null) st.push(node.right); //右
                if(node.left!=null) st.push(node.left); //左
            }else{
                node = st.pop();
                list.add(node.val);
            }
        }
    }
}

后序遍历找根节点到叶子结点的所有路径

class Solution {
    public List<List<Integer>> find_path(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        if(root==null) return list;
        Stack<TreeNode> st = new Stack<>();
        TreeNode pre = null;
        while(root!=null||!st.isEmpty()){
            while(root!=null){
                st.push(root);
                root = root.left;
            }
            root = st.peek();//取栈顶元素
            if(root.right==null||root.right==pre){ //若栈顶元素右节点为空，或右节点已被访问才访问该节点
                if(root.left==null&&root.right==null){ //若访问的结点时是叶子节点，输出路径
                    for(TreeNode node : st){//栈中元素为根节点到叶子节点的路径
                        path.add(node.val) 
                    }
                    ans.add(path);
                }
                root = st.pop();
                pre = root;
                root = null;
            }else{
                root = root.right;
            }
        }
        return ans;
    }
}