LeetCode 144. Binary Tree Preorder Traversal (With Java)

先附上题目连结

题目说明：给定一棵树，要你用前序追蹤来储存每个节点的值

前一篇文章有提到树的遍历方式有四种，这次要介绍的是前序(Preorder)的遍历。

前序探讨:首先，我们要拜访的是根(父)节点，再来是左节点，最后才是右节点。同样我使用维基百科上面的二元树图片进行说明。

以此图来说，它的preorder traversal是8-->3-->1-->6-->4-->7-->10-->14-->13，8是此树的根节点(第一个)，8有左节点3，因此3是第二个，3有左节点1，1为第三个，1没有左右节点，回到3，3有右点6，6是第四个，6有左节点4，4是第五个，4没有左右节点，因此回到6，6有右节点7，7是第六个，7没有左右节点，回到6再回到3再回到8，8有右节点10，10为第七个，10没有左节点但有右节点14，因此14是第八个，14有左节点13，13为第九个，13没有左右节点，结束此次遍历。

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

preorderTraversal(Tree root){    if(root.null) return;    else{        print(root.val);//印出root的值，如果是要用list来储存每个节点的值可以换成 list.add(root.val)        preorderTraversal(root.left);//拜访左节点        preorderTraversal(root.right);//拜访右节点    }}

在此题当中，我会使用一个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> result=new ArrayList<Integer>();//储存资料node的值    public List<Integer> preorderTraversal(TreeNode root) {        if(root==null){            return result;        }//如果根结点为空值，直接回传list        else{             result.add(root.val);//新增根节点的值             preorderTraversal(root.left);//拜访左节点             preorderTraversal(root.right);//拜访右节点        }        return result;    }}

下一篇会讲解postorder