LeetCode - Medium - 145. Binary Tree Postorder Traversal-蒲公英云

Topic

Stack, Tree

Description

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

Given a binary tree, return the postorder traversal of its nodes’ values.

Example:

Input: [1,null,2,3]
   1
    \
     2
    /
   3

Output: [3,2,1]

Follow up: Recursive solution is trivial, could you do it iteratively?

Analysis

方法一：我写的非递归版（用栈实现）

方法二：别人写的非递归版（用栈实现）

方法三：传统的非递归版

Submission

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;
import com.lun.util.BinaryTree.TreeNode;
public class BinaryTreePostorderTraversal { 
    //方法一：我写的非递归版
    public List<Integer> postorderTraversal(TreeNode root) { 
        if(root == null) { 
            throw new IllegalArgumentException();
        }
        List<Integer> result = new ArrayList<>();
        LinkedList<Object> stack = new LinkedList<>();
        TreeNode node = root;
        outter : while(true) { 
            if(node.left != null && node.right != null) { 
                stack.push(node);
                stack.push(2);
                node = node.left;
            }else if(node.left != null && node.right == null) { 
                stack.push(node);
                stack.push(1);
                node = node.left;
            }else if(node.left == null && node.right != null) { 
                stack.push(node);
                stack.push(1);
                node = node.right;
            }else { 
                result.add(node.val);
                while(true) { 
                    if(stack.isEmpty()) { 
                        break outter;
                    }
                    int count = (int)stack.pop();
                    if(count == 1) { 
                        TreeNode tmp = (TreeNode)stack.pop();
                        result.add(tmp.val);
                    }else if(count == 2) { 
                        stack.push(1);
                        node = ((TreeNode)stack.get(1)).right;
                        break;
                    }
                }
            }
        }
        return result;
    }
    //方法二：别人写的非递归版
    public List<Integer> postorderTraversal2(TreeNode root) { 
        LinkedList<Integer> ans = new LinkedList<>();
        Stack<TreeNode> stack = new Stack<>();
        if (root == null) return ans;
        stack.push(root);
        while (!stack.isEmpty()) { 
            TreeNode cur = stack.pop();
            ans.addFirst(cur.val);
            if (cur.left != null) { 
                stack.push(cur.left);
            }
            if (cur.right != null) { 
                stack.push(cur.right);
            } 
        }
        return ans;
    }
    //方法三：传统的递归版
    public List<Integer> postorderTraversal3(TreeNode root) { 
        List<Integer> result = new ArrayList<>();
        postorderTraversal3(root, result);
        return result;
    }
    private void postorderTraversal3(TreeNode root, List<Integer> list) { 
        if(root != null) { 
            postorderTraversal3(root.left, list);
            postorderTraversal3(root.right, list);
            list.add(root.val);
        }
    }
}

Test

import static org.junit.Assert.*;
import static org.hamcrest.CoreMatchers.*;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;
import org.junit.Test;
import com.lun.util.BinaryTree.TreeNode;
public class BinaryTreePostorderTraversalTest { 
    @Test
    public void test() { 
        BinaryTreePostorderTraversal obj = new BinaryTreePostorderTraversal();
        TreeNode root = new TreeNode(1);
        root.right = new TreeNode(2);
        root.right.left = new TreeNode(3);
        List<Integer> actual = obj.postorderTraversal(root);
        List<Integer> actual2 = obj.postorderTraversal2(root);
        List<Integer> actual3 = obj.postorderTraversal3(root);
        assertThat(actual, is(Arrays.asList(3,2,1)));
        assertThat(actual2, is(Arrays.asList(3,2,1)));
        assertThat(actual3, is(Arrays.asList(3,2,1)));
    }
    @Test
    public void test2() { 
        BinaryTreePostorderTraversal obj = new BinaryTreePostorderTraversal();
        //https://blog.csdn.net/qq_34840129/article/details/80619761中的图
        TreeNode root = new TreeNode('A');
        root.left = new TreeNode('B');
        root.right = new TreeNode('C');
        root.left.left = new TreeNode('D');
        root.left.right = new TreeNode('E');
        root.left.left.right = new TreeNode('H');
        root.left.right.right = new TreeNode('I');
        //---
        root.right.left = new TreeNode('F');
        root.right.right = new TreeNode('G');
        root.right.left.left = new TreeNode('J');
        root.right.left.right = new TreeNode('K');
        inorder(root);
        List<Integer> actual = obj.postorderTraversal(root);
        List<Integer> actual2 = obj.postorderTraversal2(root);
        List<Integer> actual3 = obj.postorderTraversal3(root);
        List<Integer> expect = Arrays.asList('H', 'D', 'I', 'E', 'B', 'J', 'K', 'F', 'G', 'C', 'A')
                .stream().map(a->a-'A').collect(Collectors.toList());
        assertThat(actual, is(expect));
        assertThat(actual2, is(expect));
        assertThat(actual3, is(expect));
    }
    private static void inorder(TreeNode node) { 
        if(node != null) { 
            inorder(node.left);
            node.val = node.val - 'A';
            inorder(node.right);
        }
    }
}