LeetCode 145. Binary Tree Postorder Traversal (With Java)

附上题目连结

题目：给定一棵树，求出透过postorder traversal的值

postorder探讨：首先我们要先拜访左边的节点，之后拜访右边的节点，最后拜访根(父)节点，同样透过维基百科的图片进行解说。

以此图来说，它的postorder traversal是1-->4-->7-->6-->3-->13-->14-->10-->8，首先从8开始，有左节点，持续往左到1，1没有左右节点，为第一个，回到3，3有右节点6，6有左节点4，4为第二个，4没有左右节点，回到6，6有右节点7，7为第三个，7没有左右节点，回到6，6是第四个，接着回到3，3是第五个，回到8，8有右节点10，10有右节点14，14有左节点13，13没有左右节点因此为第六个，回到14，14为第七个，回到10，10为第八个，最后回到第九个8，结束遍历。

虚拟码(表达概念，不同程式语言要考虑其语法转换)

postorderTraversal(Tree t){    if(t==null)return;    else{        postorderTraversal(t.left);//追蹤左节点        postorderTraversal(t.right);//追蹤右节点        print(t.val);//印出根节点的值(如果有要储存值可以改成list.add(t.val))    }}

在此题当中，我会使用一个List来储存树的资料并运用递迴概念来进行回传
附上程式码以及说明

/** * 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 {    List<Integer> l=new ArrayList<>();//储存node的值    public List<Integer> postorderTraversal(TreeNode root) {        if(root==null){return l;}//如果root为空值，直接回传        postorderTraversal(root.left);//追蹤左节点        postorderTraversal(root.right);//追蹤右节点        l.add(root.val);//储存root的值        return l;//回传    }}