Leetcode-145-Binary Tree Postorder Traversal

Binary Tree Postorder Traversal

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

Description:

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

Idea:

the order of prerder is left node->right node->parent node(start from the root’s left node)

**Step1: **create the method and use recurision to traverse the whole tree.

**Step2: **move the node to it’s left child and add it’s left child firstly unitl the left subtree finished, then then traverse the right child until the right subtree finished. Finally, add the parent node.

Code:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        //create the result list
        List<Integer> result = new ArrayList<Integer>();
        postorder(root,result);
        return result;
    }

    public void postorder(TreeNode root, List<Integer> result) {
        if (root == null) {
            return;
        }
        //in the inorder, firstly add the left child and start from the root's left child. 
        postorder(root.left, result);
        //then visit the right child of tree.
        postorder(root.right, result);
        //visit the parent node finally.
        result.add(root.val);
        
    }
}