leetcode算法练习【145】二叉树的后序遍历

快来打我* 2023-02-14 13:26 24阅读 0赞

### 文章目录 ###

*   *   *   *  所有题目源代码：\[Git地址\](https://github.com/ch98road/leetcode)
             *  题目
             *  方案：递归、迭代+栈
             *   *  复杂度计算

#### 所有题目源代码：[Git地址][Git] ####

#### 题目 ####

给定一个二叉树，返回它的 后序 遍历。
    
    示例:
    
    输入: [1,null,2,3]  
       1
        \
         2
        /
       3 
    
    输出: [3,2,1]
    进阶: 递归算法很简单，你可以通过迭代算法完成吗？

#### 方案：递归、迭代+栈 ####

*  后续的迭代用栈实现，和前序和中序有点不同，就是需要反着插入数组，因为父节点不太好弄得符合逻辑。。。

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
    class Solution { 
        private LinkedList<Integer> res = new LinkedList<>( );
        private Stack<TreeNode> stack = new Stack<>( );
        public List<Integer> postorderTraversal(TreeNode root) { 
            // // 递归解法
            if (root==null) return res;
            // if(root.left!=null) postorderTraversal(root.left);
            // if(root.right!=null) postorderTraversal(root.right);
            // res.add(root.val);
            // return res;
    
            //迭代解法
            //正常遍历，就是反着插入就行
            stack.push(root);
            TreeNode cur ;
            while (!stack.isEmpty( )) { 
                cur = stack.pop();
                res.addFirst(cur.val);
                if (cur.left != null) { 
                    stack.push(cur.left);
                } 
                if(cur.right!=null){ 
                    stack.push(cur.right);
                }
            }
            return res;
        }
    }

##### 复杂度计算 #####

*  时间复杂度：O(n)
 *  空间复杂度：O(n)

[Git]: https://github.com/ch98road/leetcode