[Java] LeetCode 144. Binary Tree Preorder Traversal

[Java] LeetCode 144. Binary Tree Preorder Traversal

 

문   제 : 

이진트리 root가 주어진다.

root 를 preorder로 순회한 결과를 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;
 *     }
 * }
 */

 

Example )

Input: root = [1,null,2,3]
Output: [1,2,3]

 

---

접   근 : 

DFS를 활용해 재귀함수로 접근

 

---

해   결 : 

결과값을 저장할 List를 선언해준다.

dfs 함수를 선언하고 preorder의 순서대로 Tree를 순회한다.

 

preorder의 순서 : 

Tree의 왼쪽 -> Tree의 오른쪽

 

---

 

 

List를 선언해준다.

List<Integer> n = new ArrayList<Integer>();

 

 

 

---

 

root가 비어있는지 확인해준다. (예외처리)

if(root == null) return n;

 

---

 

 

dfs함수를 선언해준다.

매개변수로는 node, 결과값을 담을 List가 들어간다.

List에 값을 저장해주고, preorder순회를 한다.

public void dfs(TreeNode node, List<Integer> n) {
    n.add(node.val);
    if(node.left != null) dfs(node.left, n);
    if(node.right != null) dfs(node.right, n);
}

 

---

결   과  :

class Solution {
   
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> n = new ArrayList<Integer>();
        
        if(root == null) return n;
        
        dfs(root, n);
        return n;
    }
    public void dfs(TreeNode node, List<Integer> n) {
        n.add(node.val);
        if(node.left != null) dfs(node.left, n);
        if(node.right != null) dfs(node.right, n);
    }
}