Leetcode 145. 二叉树的后序遍历非迭代YYDS

怼烎@ 2022-09-03 13:12 66阅读 0赞

#### 题目重述 ####

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

示例:

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

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

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/binary-tree-postorder-traversal  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

#### 思路一 ####

后序遍历就是 根右左遍历的反转

#### Java实现 ####

class Solution {
        
        public List<Integer> postorderTraversal(TreeNode root) {
        
            List<Integer> result = new ArrayList<>();
            if (root == null) {
        
                return result;
            }
            // 根-右-左正好是后序遍历的逆序
            Stack<TreeNode> stack = new Stack<>();
            while (root != null || !stack.empty()) {
        
                while (root != null) {
        
                    // 根-右
                    result.add(root.val);
                    stack.push(root);
                    root = root.right;
                }
                // 出栈转左
                root = stack.pop().left;
            }
            // 反转即可
            Collections.reverse(result);
            return result;
        }
    }

#### 思路二 ####

二叉树的遍历顺序是左-> 右 -> 中，整体思路也是这样，不断地寻找最左的，当找不到转而去找右的最左。

需要注意的是，记得保存前驱。

1.  不断将左节点入栈，直到左节点为空
2.  回退到当前结点的父节点，判断右结点是否为空，对右节点继续执行第一步迭代

#### Java实现 ####

class Solution {
        
        public List<Integer> postorderTraversal(TreeNode root) {
        
            List<Integer> result = new ArrayList<>();
            if(root == null)
            {
        
                return result;
            }
            Stack<TreeNode> stack = new Stack<>();
            TreeNode prev = null;
            while (root  != null ||!stack.empty() ){
        
                // 第一步：不断遍历左子树，加进栈中，直到左子树为空
                while (root != null)
                {
        
                    stack.push(root);
                    root = root.left;
                }
                // 第二步：当左子树为空时，转而转向右子树
                root = stack.pop();
                // 右子树为空，或者前驱就是root 则保存结果
                if (root.right == null || root.right == prev) {
        
                    result.add(root.val);
                    // 保存前驱结点
                    prev = root;
                    root = null;
                }
                // 右子树不为空，继续对左子树执行第一步
                else {
        
                    stack.push(root);
                    root = root.right;
                }
            }
            return  result;
        }
    }