Node definition

public static class BinaryNode<T> {
    T element;
    BinaryNode<T> left;
    BinaryNode<T> right;
    BinaryNode(T theElement) {
        this(theElement, null, null);
    }
    BinaryNode(T theElement, BinaryNode<T> lt, BinaryNode<T> rt) {
        element = theElement;
        left = lt;
        right = rt;
    }
}

Binary tree nodes include element values and left and right child node references .

Create nodes

BinaryNode g = new BinaryNode(7);
BinaryNode f = new BinaryNode(6);
BinaryNode e = new BinaryNode(5);
BinaryNode d = new BinaryNode(4);
BinaryNode c = new BinaryNode(3, f, g);
BinaryNode b = new BinaryNode(2, d, e);
BinaryNode a = new BinaryNode(1, b, c);

Form like ：

1、 front 、 in 、 After the sequence traversal

In front of the binary tree 、 in 、 Before in postorder traversal 、 in 、 The root node ;
Before the order ： Output the root node first , And then the left and right nodes .
Middle preface ： First left , Then output the root node , To the right .
In the following order ： First left and right , Then output the root node .

public static void visit(BinaryNode p) {
    System.out.print(p.element + " ");
}

1.1、 The former sequence traversal

 root -> Left -> Right 
1 2 4 5 3 6 7

1.1.1、 Recursive implementation

 public static void recursivePreOrder(BinaryNode p) {
    if (p == null) return;
    visit(p);
    recursivePreOrder(p.left);
    recursivePreOrder(p.right);
}

If the node is null, Go straight back to ;
Print out the root node first , Then recursion left subtree , Then recurs the right subtree .
Just meet ： First root , And then around .

1.1.2、 Non recursive implementation

public static void iterativePreOrder(BinaryNode p) {
    if (p == null) return;
    Stack<BinaryNode> stack = new Stack<>();
    stack.push(p);
    while (!stack.empty()) {
        p = stack.pop();
        visit(p);
        if (p.right != null) stack.push(p.right);
        if (p.left != null) stack.push(p.left);
    }
}

Make full use of the idea of stack , First in, then out .
When the node is not empty , Putting nodes on the stack , Iterate the elements in the stack , Pop up top element , Currently the root element , After that, press the right and left child nodes on the stack respectively . In this way, the order of the child nodes is left first and then right .

1.2、 In the sequence traversal

 Left -> root -> Right 
4 2 5 1 6 3 7

1.2.1、 Recursive implementation

public static void recursiveInOrder(BinaryNode p) {
    if (p == null) return;
    recursiveInOrder(p.left);
    visit(p);
    recursiveInOrder(p.right);
}

1.2.2、 Non recursive implementation

public static void iterativeInOrder(BinaryNode p) {
    if (p == null) return;
    Stack<BinaryNode> stack = new Stack<>();
    while (!stack.empty() || p != null) {
        while (p != null) {
            stack.push(p);
            p = p.left;
        }
        p = stack.pop();
        visit(p);
        p = p.right;
    }
}

1.3、 After the sequence traversal

 Left -> Right -> root 
4 5 2 6 7 3 1

1.3.1、 Recursive implementation

public static void recursivePostOrder(BinaryNode p) {
    if (p == null) return;
    recursivePostOrder(p.left);
    recursivePostOrder(p.right);
    visit(p);
}

1.3.2、 Non recursive implementation

public static void iterativePostOrder(BinaryNode p) {
    if (p == null) return;
    Stack<BinaryNode> stack = new Stack<>();
    Stack<BinaryNode> result = new Stack<>();
    while (!stack.empty() || p != null) {
        while (p != null) {
            stack.push(p);
            result.push(p);
            p = p.right;
        }
        if (!stack.empty()) p = stack.pop().left;
    }
    while (!result.empty()) {
        p = result.pop();
        visit(p);
    }
}

2、BFS And DFS

2.1、BFS Breadth first search

1234567

Breadth first traversal is to read node elements by layer , We need to use the data structure of the queue .

public static void levelOrderTraversal(BinaryNode node) {
    if (node == null) {
        System.out.print("empty tree");
        return;
    }
    LinkedList<BinaryNode> queue = new LinkedList<>();
    queue.add(node);
    while (!queue.isEmpty()) {
        BinaryNode binaryNode = queue.pollFirst();
        System.out.print(binaryNode.element + "  ");
        if (binaryNode.left != null) {
            queue.add(binaryNode.left);
        }
        if (binaryNode.right != null) {
            queue.add(binaryNode.right);
        }
    }
}

2.2、DFS Depth-first search

1245367

Starting from the root node , Select a branch to read all the elements , We need to use the data structure of the stack .

public static void depthTraversal(BinaryNode node) {
    if (node == null) {
        System.out.print("empty tree");
        return;
    }
    LinkedList<BinaryNode> stack = new LinkedList<>();
    stack.push(node);
    while (!stack.isEmpty()) {
        BinaryNode binaryNode = stack.pop();
        System.out.print(binaryNode.element);
        if (binaryNode.right != null) {
            stack.push(binaryNode.right);
        }
        if (binaryNode.left != null) {
            stack.push(binaryNode.left);
        }
    }
}

3、 The depth of the binary tree

104. The maximum depth of a binary tree

3.1、 recursive

private static int calcDepth(BinaryNode node) {
    if (node == null) return 0;
    int ld = calcDepth(node.left);
    int rd = calcDepth(node.right);
    if (ld > rd) {
        return ld + 1;
    } else {
        return rd + 1;
    }
}

3.2、 Depth first

maxDepth Compare the length of each branch to update , Finally get the deepest branch length .

public static int maxDepthDFS(BinaryNode node) {
    if (node == null) return 0;
    LinkedList<BinaryNode> stack = new LinkedList<>();
    LinkedList<Integer> value = new LinkedList<>();
    stack.push(node);
    value.push(1);
    int maxDepth = 0;
    while (!stack.isEmpty()) {
        BinaryNode binaryNode = stack.pop();
        int temp = value.pop();
        maxDepth = Math.max(temp, maxDepth);
        if (binaryNode.right != null) {
            stack.push(binaryNode.right);
            value.push(temp + 1);
        }
        if (binaryNode.left != null) {
            stack.push(binaryNode.left);
            value.push(temp + 1);
        }
    }
    return maxDepth;
}

3.3、 breadth-first

Search by layer , Every step into the floor , depth +1.

public static int maxDepthBFS(BinaryNode node) {
    if (node == null) return 0;
    LinkedList<BinaryNode> queue = new LinkedList<>();
    queue.add(node);
    int maxDepth = 0;
    while (!queue.isEmpty()) {
        maxDepth++;
        BinaryNode binaryNode = queue.pollFirst();
        if (binaryNode.left != null) {
            queue.add(binaryNode.left);
        }
        if (binaryNode.right != null) {
            queue.add(binaryNode.right);
        }
    }
    return maxDepth;
}

4、 Binary tree image

Traverse by depth or breadth , Swap the left and right subtrees of nodes .

public static void mirror(BinaryNode root) {
    if (root == null) return;
    LinkedList<BinaryNode> stack = new LinkedList<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        BinaryNode node = stack.pop();
        BinaryNode temp = node.left;
        node.left = node.right;
        node.right = temp;
        if (node.right != null) {
            stack.push(node.right);
        }
        if (node.left != null) {
            stack.push(node.left);
        }
    }
}

5、 Symmetric binary tree

101. Symmetric binary tree
This problem is a variation of binary tree mirror image , If two binary trees are symmetric , be ：

1. Two root nodes have the same value
2. The left subtree of each tree , Are the same as the right subtree of another tree
   Recursive implementation ：

   public boolean isSymmetric(BinaryNode root) {
       return isMirror(root, root);
   }
   
   public boolean isMirror(BinaryNode t1, BinaryNode t2) {
       if (t1 == null && t2 == null) return true;
       if (t1 == null || t2 == null) return false;
       return (t1.val == t2.val)
           && isMirror(t1.right, t2.left)
           && isMirror(t1.left, t2.right);
   }

   Iterative implementation ：

   public boolean isSymmetric(BinaryNode root) {
       LinkedList<BinaryNode> q = new LinkedList<>();
       q.add(root);
       q.add(root);
       while (!q.isEmpty()) {
           BinaryNode t1 = q.poll();
           BinaryNode t2 = q.poll();
           if (t1 == null && t2 == null) continue;
           if (t1 == null || t2 == null) return false;
           if (t1.val != t2.val) return false;
           q.add(t1.left);
           q.add(t2.right);
           q.add(t1.right);
           q.add(t2.left);
       }
       return true;
   }

summary

The algorithm of various topics of binary tree will think of recursion in the first consciousness , But when the recursion depth is too large, there will be stack overflow , So iterations will be used to implement accordingly , Accordingly, the data structure of queue or stack is introduced .
It feels like the most important algorithm is DFS And BFS, among DFS Depth first search uses the FIFO feature of the stack , and BFS Breadth first search uses the first in first out feature of the queue .