LeetCode Day 11 Binary Tree Part 1

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.

so if the parent node is i, the left child will be i*2+1, and the right child will be i*2 + 2

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:

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

    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

    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; 
    }