[LeetCode] Binary Tree Inorder Traversal

leetcode.com/explore/interview/card/top-interview-questions-medium/108/trees-and-graphs/786/

 

 

이진 트리!!!! 이론을 공부해도 코드로 구현하기는 녹록치 않다 💬

30분동안 푼 내용..문제 해석하느라 정신이 없었다.

노드를 순회하는 순서와 재귀함수를 써서 반복해야 하는것은 알았지만 코드 정리가 안되고 헤매는 모습😅

메서드를 새로 생성해도 된다는 생각을 못하고 해당 메서드 안에서만 풀려고하니까 이래저래 더 꼬인듯하다.

public class BinaryTree0310 {

	public List<Integer> inorderTraversal(TreeNode root) {
		//순서대로 처음에 들어오는 root가 루트노드
		//그 다음이 left
		//그 다음이 right
		//반복
		List<Integer> list = new ArrayList<Integer>();
		if(root!=null) {
			//첫번째 배열 정렬
			list.add(root.val);

			//해당 루트로 새로 세팅 (?) 어디에서 세팅해야할까
			TreeNode tree = new TreeNode(root.val);

		}else if(root==null) {

		}

		//중위순회는 left - root - right 순으로 순회
		//root가 정해질 때마다 왼쪽 값 있는지 확인
		//있으면 먼저 정렬


		return list;
	}

}

 

결국 정답을 보고 이해해보기로 했다.

 

Pseudocode (수도코드)

inorder (node)
if node = null then return
inorder (node.left)
visit (node)
inorder (node.right)

➡ O(N0 한번 씩 모두 방문

 

class Solution {
    public List < Integer > inorderTraversal(TreeNode root) {
        List < Integer > res = new ArrayList < > ();
        helper(root, res);
        return res;
    }

    public void helper(TreeNode root, List < Integer > res) {
        if (root != null) {
            if (root.left != null) {
                helper(root.left, res);
            }
            res.add(root.val);
            if (root.right != null) {
                helper(root.right, res);
            }
        }
    }
}

 

스택을 활용해서 푸는 방법도 있었다.

public class Solution {
    public List < Integer > inorderTraversal(TreeNode root) {
        List < Integer > res = new ArrayList < > ();
        Stack < TreeNode > stack = new Stack < > ();
        TreeNode curr = root;
        while (curr != null || !stack.isEmpty()) {
            while (curr != null) {
                stack.push(curr);
                curr = curr.left;
            }
            curr = stack.pop();
            res.add(curr.val);
            curr = curr.right;
        }
        return res;
    }
}

 

메서드를 만들지 않고 푸는 법

class Solution {
    public List < Integer > inorderTraversal(TreeNode root) {
        List < Integer > res = new ArrayList < > ();
        TreeNode curr = root;
        TreeNode pre;
        while (curr != null) {
            if (curr.left == null) {
                res.add(curr.val);
                curr = curr.right; // move to next right node
            } else { // has a left subtree
                pre = curr.left;
                while (pre.right != null) { // find rightmost
                    pre = pre.right;
                }
                pre.right = curr; // put cur after the pre node
                TreeNode temp = curr; // store cur node
                curr = curr.left; // move cur to the top of the new tree
                temp.left = null; // original cur left be null, avoid infinite loops
            }
        }
        return res;
    }
}