Before the beginning of the article, first put a portal binary tree characteristics and Java implementation OF DFS, BFS. So, in this article, we will look at the three basic problems of binary tree in LeetCode: middle order traversal, pre-order traversal, post-order traversal, and layer order traversal. In fact, the solution is really nothing to say, are eight-essay…

Middle order traversal of binary tree ²

Given a binary tree, return its middle-order traversal.

Example:

Input: [1, NULL,2,3] 1\2/3 Output: [1,3,2]Copy the code

Solution one: recursion

Middle order: left root right, just change the root to add()

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        inOrder(root,res);
        return res;
    }

    private void inOrder(TreeNode node,List res) {
        if (node == null) return; inOrder(node.left,res); res.add(node.val); inOrder(node.right,res); }}Copy the code

Solution two: iteration

Recursion maintains a stack of function calls internally, whereas iteration holds all the nodes on a stack, goes off the stack and evaluates them

public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
		
        // root=null, a non-null judgment of the tree
        // stack.isEmpty, the tree traversal judgment
        while(root ! =null| |! stack.isEmpty()) {// Traverses all left subtrees of the current node
            while(root ! =null) {
                stack.push(root);
                root = root.left;
            }
	        // The top of the stack is now the leftmost node, off the stack, value
            root = stack.pop();
            res.add(root.val);
            
            // Process the next node (subtree)
            Root =root.right==null, but stack is not Empty, so push out the parent node of the current node
     		// 2. Before the leaf node is reached, root=root.right, traverses the right child node of the current node
            root = root.right;
        }
        return res;
    }
Copy the code

144. Preorder traversal of binary tree ²

Given a binary tree, return its prior traversal.

Example:

Input: [1, NULL,2,3] 1\2/3 Output: [1,2,3]Copy the code

Solution one: recursion

Preorder: around the root, just replace the root with add()

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        preOrder(root ,res);
        return res;
    }

    public void preOrder(TreeNode root,List<Integer> res) {
        if (root == null) return; res.add(root.val); preOrder(root.left, res); preOrder(root.right, res); }}Copy the code

Solution two: iteration

public List<Integer> preorderTraversal(TreeNode root) {
    
    List<Integer> res = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
		
    stack.push(root);
    while(! stack.empty()){ root = stack.pop(); res.add(root.val);if(root.right ! =null) stack.push(root.right);
        if(root.left ! =null) stack.push(root.left);
    }
    return res;
}
Copy the code

145. Post-order traversal of binary trees ³

Given a binary tree, return its backward traversal.

Example:

Input: [1, NULL,2,3] 1\2/3 Output: [3,2,1]Copy the code

Solution one: recursion

After order: left and right root, just replace the root with add()

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        postOrder(root,res);
        return res;
    }

    public void postOrder(TreeNode root, List<Integer> res) {
        if (root == null) return; postOrder(root.left,res); postOrder(root.right,res); res.add(root.val); }}Copy the code

Solution 2: iteration *

public List<Integer> postorderTraversal(TreeNode root) {

    List<Integer> res = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
		
    stack.push(root);
    while(! stack.empty()){ root = stack.pop(); res.add(0, root.val); / / head
        if(root.left ! =null) stack.push(root.left); // The reverse of the preceding traversal
        if(root.right ! =null) stack.push(root.right);
    }
    return res;
}
Copy the code

Order traversal of binary tree ²

Given a binary tree, return the values of nodes traversed in order. (That is, layer by layer, all nodes are accessed from left to right).

Example: binary tree: [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7
Copy the code

Returns the result of its hierarchical traversal:

[[3], [9,20], [15,7]Copy the code

Method: the BFS

public List<List<Integer>> levelOrder(TreeNode root) {
        if (root == null) return new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        List<List<Integer>> res = new ArrayList<>();

        while(! queue.isEmpty()) { List<Integer> list =new ArrayList<>();
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                list.add(node.val);
                if(node.left ! =null) queue.offer(node.left);
                if(node.right ! =null) queue.offer(node.right);
            }
            res.add(list);
        }
        return res;
    }
Copy the code