LeetCode Day 12
Tags: leetcode, java, datastructures
Published: 2024-06-19 14:06:28

# 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:

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/4ro7frjlbzjb2yw0ma5r.png)
>Input: root = [4,2,7,1,3,6,9]
>Output: [4,7,2,9,6,3,1]

Example 2:


Example 2:
![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/qqjij6j6utvl6kdxcg0d.png)
> 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

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/p4v0v8c1cynqgjfllv86.png)
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();
    }
```