[数据结构与算法]LeetCode 刷题系列-- 二叉树遍历

1. 二叉树前序遍历

LeetCode题目链接：力扣

前序遍历的顺序为：根左右

1.1? 递归：

import java.util.ArrayList;
import java.util.List;



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

    public void preorderTraversal(TreeNode root, List<Integer> result) {
        if (root.left == null && root.right == null) {
            result.add(root.val);
            return;
        }

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

}

1.2 迭代：

import java.util.ArrayList;
import java.util.List;

/**
     * 二叉树前序遍历迭代法
     * 利用 Stack
     * 1. 根节点存放入 Stack中
     * 2. 将栈顶元素弹出，并将弹出元素的右子节点压入Stack，再将元素的左子节点压入Stack
     * 3. 重复2，直到Stack为空
     */

class Solution {
       public List<Integer> preorderTraversal(TreeNode root) {
          List<Integer> result = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        
        if(root !=null) {
            stack.push(root);
        }
        
        while (!stack.isEmpty()) {
            TreeNode currentNode = stack.pop();
            result.add(currentNode.val);
            if(currentNode.right !=null) {
                stack.push(currentNode.right);
            }
            if(currentNode.left !=null) {
                stack.push(currentNode.left);
            }
        }
        
        return result;
    }


}

2. 中序遍历

LeetCode题目链接：力扣

中序遍历的顺序为：左根右

2.1? 递归

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();

        if (root != null) {
            inorderTraversal(root, result);
        }
        return result;
    }


    public void inorderTraversal(TreeNode root, List<Integer> result) {
        if (root.left == null && root.right == null) {
            result.add(root.val);
            return;
        }
        if (root.left != null) {
            inorderTraversal(root.left, result);
        }
        result.add(root.val);
        if (root.right != null) {
            inorderTraversal(root.right, result);
        }
    }
}

2.2? 迭代

class Solution {
     /**
     * 二叉树中序遍历，迭代
     * 1. 将根节点，压入栈中
     * 2. peek栈顶元素，如果栈顶元素的左子节点不为空，则将栈顶元素的左子节点压入栈，直到栈顶元素无左子节点为止
     * 3. 弹出栈顶元素，
     * 3.1 若当前元素有右子节点，则执行 2；
     * 3.2 否则 继续执行 3
     * 4. 重复执行 2 与 3
     *
     * @param root
     * @return
     */
    public List<Integer> inorderTraversal1(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();

        if (root != null) {
            stack.push(root);

            TreeNode currentNode = stack.peek();
            while (currentNode.left != null) {
                stack.push(currentNode.left);
                currentNode = stack.peek();
            }
            while (!stack.isEmpty()) {
                TreeNode currentNode1 = stack.pop();
                result.add(currentNode1.val);
                if (currentNode1.right != null) {
                    stack.push(currentNode1.right);
                    TreeNode currentNode2 = stack.peek();

                    while (currentNode2.left != null) {
                        stack.push(currentNode2.left);
                        currentNode2 = stack.peek();
                    }
                }
            }
        }
        return result;
    }

}

3. 后序遍历

LeetCode题目链接：力扣

后序遍历的顺序为：左右根

3.1? 递归

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root != null) {
            postorderTraversal(root, result);
        }
        return result;
    }

    public void postorderTraversal(TreeNode root, List<Integer> result) {
        if (root.left == null && root.right == null) {
            result.add(root.val);
            return;
        }
        if (root.left != null) {
            postorderTraversal(root.left, result);
        }
        if (root.right != null) {
            postorderTraversal(root.right, result);
        }
        result.add(root.val);

    }
}

3.2? 迭代

class Solution {
  /**
     * 二叉树后续遍历，迭代
     * 1. 将根节点压入栈
     * 2. 依次将栈顶元素的左子节点压入栈，直到栈顶节点无左子节点为止
     * 2.1 若是当前栈顶节点无右子节点或者 prev == 当前栈顶节点的右子节点，则出栈, 令 prev = 出栈节点
     * 2.2 若是当前栈顶节点有右子节点，则将当前栈顶节点的右子节点压入栈中，并重复2
     */
    public List<Integer> postorderTraversal1(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();

        if (root != null) {
            stack.push(root);
            TreeNode currentNode1 = stack.peek();
            while (currentNode1.left != null) {
                stack.push(currentNode1.left);
                currentNode1 = stack.peek();
            }
            TreeNode prev = null;
            while (!stack.isEmpty()) {
                TreeNode currentNode2 = stack.peek();

                if (currentNode2.right == null || currentNode2.right == prev) {
                    stack.pop();
                    result.add(currentNode2.val);
                    prev = currentNode2;
                } else if (currentNode2.right != null) {
                    currentNode2 = currentNode2.right;
                    stack.push(currentNode2);
                    while (currentNode2.left != null) {
                        currentNode2 = currentNode2.left;
                        stack.push(currentNode2);
                    }
                }
            }
        }
        return result;
    }
}

4.层序遍历

LeetCode 题目链接： 力扣

层序遍历：一层一层的遍历

class Solution {
 /**
     * 层序遍历
     * 1. 将根节点压入队列，并压入分层标记，null (因为 Java 的队列不允许压入null，这里直接压入 val 为-1111的节点到队列)
     * 2. 将 队列的头部节点弹出，并判断头部节点的左子节点是否为null ，不为null的话头部节点的左子节点压入队列；
     *     判断头部节点的右子节点是否为null ，不为null的话头部节点的右子节点压入队列;
     * 3. 重复 2 直到弹出的头部节点的 val == -1111 （标识位），则说明该层已经遍历完，同时将标志位压入队列
     * 4. 重复 3
     * @param root
     * @return
     */
    public List<List<Integer>> levelOrder(TreeNode root) {
        Queue<TreeNode> queue = new LinkedBlockingQueue<>();
        List<List<Integer>> result = new LinkedList<>();
        if (root == null) {
            return result;
        }
        queue.offer(root);
        queue.add(new TreeNode(-1));
        while (!queue.isEmpty()) {
            List<Integer> subList = new LinkedList<>();
            TreeNode currentNode = queue.poll();
            while (currentNode != null && currentNode.val != -1) {
                if (currentNode.left != null) {
                    queue.add(currentNode.left);
                }
                if (currentNode.right != null) {
                    queue.add(currentNode.right);
                }
                subList.add(currentNode.val);
                currentNode = queue.poll();
            }
            if (subList.isEmpty()) {
                break;
            }
            result.add(subList);
            queue.add(new TreeNode(-1));
        }
        return result;
    }

}