LeetCode Day 11 Binary Tree Part 1
Tags: leetcode, java, datastructures
Published: 2024-06-18 14:08:01

# Tree Structure 

2 ways to realize Binary Tree
1, Linked method. Similar to a Linked list, use logical linking by references instead of a physically linked data structure 

2, Array is a physically linked data structure and we can realize it in logic as well. 
e.g. 
![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/9olu8wnj20nm3n58aai0.png)
so if the parent node is i, the left child will be i*2+1, and the right child will be i*2 + 2

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/tprcsfaytxqoz4zyas2w.png)

And if the Tree is not Binary Tree and it is a tree that each parent has 3 children. In this circumstance, if the parent node is i, the child from left to right, the 1st child will be i*3+1, the 2nd child will be i*3+2, the 3rd child will be i*3 +3 etc. 

And the normal init Tree is easy to realize:
```
public class MyTree {
	
	public class TreeNode<E> {
		
		public E val;
		public TreeNode<E> lefTNode;
		public TreeNode<E> rightNode;
		
		public TreeNode() {

		}
		
		public TreeNode(E val){
			this.val = val;
			
		}
		
		public TreeNode(E val, TreeNode<E> leftNode, TreeNode<E> rightNode) {
			this.val = val;
			this.lefTNode = leftNode;
			this.rightNode = rightNode;
			
		}
		
		
		
 	}
```

There are 4 methods to traverse binary Tree
1, Preorder: mid -> left -> right
2,Inorder: left -> mid -> right
3,Postorder: left -> right -> mid
4,levelorder: array order



# LeetCode No.144 Binary Tree Preorder Traversal
Given the root of a binary tree, return the preorder traversal of its nodes' values.
Example 1:
![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/mlu5i5oacqbjmitsh8lt.png)
> Input: root = [1,null,2,3]
> Output: [1,2,3]

Example 2:
>Input: root = []
>Output: []

Example 3:
>Input: root = [1]
>Output: [1]

### 1.
```
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if(root != null){

        list.add(root.val);
        if(root.left!=null){
            list.addAll(preorderTraversal(root.left));
            }
        if(root.right!=null){
            list.addAll(preorderTraversal(root.right));
            }

        } 
        return list;  
    }
```

### 2.
```

```


# LeetCode No. 94 Binary Tree Inorder Traversal
[Original Page](https://leetcode.com/problems/binary-tree-inorder-traversal/description/)

```
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if(root != null){
            list.addAll(inorderTraversal(root.left));
            list.add(root.val);
            list.addAll(inorderTraversal(root.right));
        }

        return list;
    }
```

# LeetCode No. 145. Binary Tree Postorder Traversal
[Original Page](https://leetcode.com/problems/binary-tree-postorder-traversal/description/)

```
    public List<Integer> postorderTraversal(TreeNode root) { 
           List<Integer> list = new ArrayList<>();
           if(root != null){
            list.addAll(postorderTraversal(root.left));
            list.addAll(postorderTraversal(root.right));
            list.add(root.val);
           }
           return list; 
    }
```