You've successfully subscribed to The Daily Awesome
Great! Next, complete checkout for full access to The Daily Awesome
Welcome back! You've successfully signed in.
Success! Your account is fully activated, you now have access to all content.
Success! Your billing info is updated.
Billing info update failed.

145. 二叉树的后序遍历 - Binary Tree Postorder Traversal

. 1 min read

145. 二叉树的后序遍历 - Binary Tree Postorder Traversal

【后序遍历-递归】【后序遍历-迭代】【后序遍历-先序的变异】

给定一个二叉树,返回它的 后序 遍历。题目描述

Example:

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

输出: [3,2,1]

Solutions

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

Solution 【后序遍历-递归】 ( 0ms)

class Solution {
    
    List<Integer> result =new ArrayList<Integer>();
    
    public List<Integer> postorderTraversal(TreeNode root) {
        loop(root);
        return result;
    }
    /* 单独写递归循环,减少return的次数 */
    public void loop(TreeNode node){
        if(node==null)
            return;
        loop(node.left);
        loop(node.right);
        result.add(node.val);
    }
}

Solution 【后序遍历-迭代】 ( 2ms)

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        if(root == null)
            return result;
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode pre = null;
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode curr = stack.peek();            
            if((curr.left == null && curr.right == null) ||
               (pre != null && (pre == curr.left || pre == curr.right))){
                result.add(curr.val);
                pre = curr;
                stack.pop();
            }else{/* 先将右结点压栈, 再将左结点入栈 */
                if(curr.right != null) 
                    stack.push(curr.right); 
                if(curr.left != null) 
                    stack.push(curr.left);   
            }            
        }
        return result;        
    }
}

Solution 【后序遍历-先序的变异】 ( 2ms)

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        if(root == null)
            return result;
        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode node = stack.pop();
            if(node.left != null) stack.push(node.left);//和传统先序遍历不一样,先将左结点入栈
            if(node.right != null) stack.push(node.right);//后将右结点入栈
            result.add(0,node.val);                        //逆序添加结点值
        }     
        return result;
    }
}

Notes