LeetCode Day 12

#leetcode #java #datastructures

144. Binary Tree Preorder Traversal

Use iteration instead of recursion

    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        //mid -> left -> right
        Deque<TreeNode> stack = new LinkedList<>();
        stack.push(root);

        while(!stack.isEmpty()){
           TreeNode cur = stack.pop();
            if(cur!=null){
                list.add(cur.val);
                stack.push(cur.right);                
                stack.push(cur.left);
            }
        }

        return list;  
    }

LeetCode No. 226. Invert Binary Tree

Given the root of a binary tree, invert the tree, and return its root.

Example 1:

Input: root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]

Example 2:

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

Example 3:

Input: root = []
Output: []

Constraints:

The number of nodes in the tree is in the range [0, 100].
-100 <= Node.val <= 100

BFS, Iteration ways

    public TreeNode invertTree(TreeNode root) {
        if(root == null){
            return null;
        }
        TreeNode cur = root;
        Deque<TreeNode> queue = new ArrayDeque<>();
        queue.offer(cur);

        while(!queue.isEmpty()){
            if(cur!=null){
                cur = queue.poll();
                TreeNode temp = cur.left; 
                cur.left = cur.right;
                cur.right = temp;
                if(cur.left != null){
                    queue.offer(cur.left);
                }
                if(cur.right !=null){
                    queue.offer(cur.right);
                }

            }
        }
        return root;

    }

Refine It

Here this evaluation is useless because if the element is in queue it must be non-null (We use offer() to add elements and it will cause NullPointer Exception it offered elements are null)

LeetCode No. 101. Symmetric Tree

Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).

    public boolean isSymmetric(TreeNode root) {
    if (root == null) {
        return true;
    }

    Deque<TreeNode> leftQ = new LinkedList<>();
    Deque<TreeNode> rightQ = new LinkedList<>();

    leftQ.offer(root.left);
    rightQ.offer(root.right);

    while (!leftQ.isEmpty() && !rightQ.isEmpty()) {
        TreeNode left = leftQ.poll();
        TreeNode right = rightQ.poll();

        if (left == null && right == null) {
            continue;
        }
        if (left == null || right == null) {
            return false;
        }
        if (left.val != right.val) {
            return false;
        }

            leftQ.offerLast(left.left);
            leftQ.offerLast(left.right);
            rightQ.offerLast(right.right);
            rightQ.offerLast(right.left);

    }


    return leftQ.isEmpty() && rightQ.isEmpty();
    }