iT邦幫忙

0

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


圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言