Trees and Graphs: Medium Part 1

Binary Tree Inorder Traversal

/**
 * 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 {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        helper(root, result);
        
        return result; 
    }
    
    private void helper(TreeNode root, List<Integer> result) {
        if (root != null) {
            if (root.left != null) {
                helper(root.left, result);
            }
            
            result.add(root.val);
            
            if (root.right != null) {
                helper(root.right, result);
            }
            
        }
        
    }
}

전에도 같은 방식으로 풀었었네요
Result 넣어주면 그대로 업데이트 된다는게 신기함다,,

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        
        result = []
        
        self.helper(root, result)
        
        return result
        
    def helper(self, root: TreeNode, result: List[int]):
        if root:
            if root.left:
                self.helper(root.left, result)                

            result.append(root.val)
            
            if root.right:
                self.helper(root.right, result)
        

이선이로도 연습해봤읍니다..
실력 심각하네요

Binary Tree Zigzag Level Order Traversal

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
  public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    if (root == null) {
      return new ArrayList<List<Integer>>();
    }

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

    LinkedList<TreeNode> node_queue = new LinkedList<TreeNode>();
    node_queue.addLast(root);
    node_queue.addLast(null);

    LinkedList<Integer> level_list = new LinkedList<Integer>();
    boolean is_order_left = true;

    while (node_queue.size() > 0) {
      TreeNode curr_node = node_queue.pollFirst();
      if (curr_node != null) {
        if (is_order_left)
          level_list.addLast(curr_node.val);
        else
          level_list.addFirst(curr_node.val);

        if (curr_node.left != null)
          node_queue.addLast(curr_node.left);
        if (curr_node.right != null)
          node_queue.addLast(curr_node.right);

      } else {
        // we finish the scan of one level
        results.add(level_list);
        level_list = new LinkedList<Integer>();
        // prepare for the next level
        if (node_queue.size() > 0)
          node_queue.addLast(null);
        is_order_left = !is_order_left;
      }
    }
    return results;
  }
}

냅다외워..ㅠㅠ

Construct Binary Tree from Preorder and Inorder Traversal

class Solution {
  int pre_idx = 0;
  int[] preorder;
  int[] inorder;
  HashMap<Integer, Integer> m = new HashMap<Integer, Integer>();

  public TreeNode helper(int l, int r) {
    if (l == r)
      return null;

    int root_val = preorder[pre_idx];
    TreeNode root = new TreeNode(root_val);

    int index = m.get(root_val);

    pre_idx++;
    root.left = helper(l, index);
    root.right = helper(index + 1, r);
    return root;
  }

  public TreeNode buildTree(int[] preorder, int[] inorder) {
    this.preorder = preorder;
    this.inorder = inorder;

    int idx = 0;
    for (Integer val : inorder)
      m.put(val, idx++);
    return helper(0, inorder.length);
  }
}

냅다 외워2...^^
이건 외우기 실패했었네요

Populating Next Right Pointers in Each Node

/*
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;

    public Node() {}
    
    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, Node _left, Node _right, Node _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
};
*/

class Solution {
    public Node connect(Node root) {
        if (root == null) {
            return root;
        }
        
        Node leftmost = root;
        
        while (leftmost.left != null) {
            Node head = leftmost;
            
            while (head != null) {
                head.left.next = head.right;
            
                if (head.next != null) {
                    head.right.next = head.next.left;
                }
                
                head = head.next;
            }
            
            leftmost = leftmost.left;
                

        }
        
        return root;
    }

}

왼쪽을 잡아서 왼쪽 다음 -> 오른쪽
다음게 있다면 오른쪽 다음 -> 다음 왼쪽
헤드, 레프트 한쪽씩 띄우는 방법~~