二叉树的三种遍历方式的代码实现

目录

• 前序遍历
• 中序遍历
• 后序遍历

前序遍历

leetcode前序遍历

 

---

 

递归遍历

    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        traversal(ans, root);
        return ans;
    }

    private void traversal(List<Integer> ans, TreeNode root) {
        // 递归的结束条件。
        if (null == root) {
            return;
        }

        ans.add(root.val);
        // 遍历左子树。
        traversal(ans, root.left);
        // 遍历右子树
        traversal(ans, root.right);
    }

迭代遍历

第一种方式

 

 public List<Integer> preorderTraversal(TreeNode root) {
        // 存放最终的结果。
        List<Integer> ans = new LinkedList<>();
        // 前序遍历使用的栈。
        Deque<TreeNode> stack = new LinkedList<>();

        while (!stack.isEmpty() || null != root) {
            // 加入左节点.
            while (null != root) {
                stack.push(root);
                // 因为是前序遍历将节点的值加入ans中。
                ans.add(root.val);
                root = root.left;
            }

            // 遍历右子树。
            root = stack.pop().right;
        }

        return ans;
    }

 

第二种方式

 

 

 public List<Integer> preorderTraversal(TreeNode root) {
        // 存储节点值的集合。
        List<Integer> ans = new LinkedList<>();
        // 二叉树为空，直接返回集合。
        if (null == root) {
            return ans;
        }

        // 遍历二叉树使用的栈。
        Deque<TreeNode> stack = new LinkedList<>();
        stack.push(root);

        // 前序遍历
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            if (null != node) {
                // 压入右节点。
                if (null != node.right) {
                    stack.push(node.right);
                }

                // 压入左节点。
                if (null != node.left) {
                    stack.push(node.left);
                }

                // 压入根节点。
                stack.push(node);
                // 压入一个null值，作为分隔符。
                stack.push(null);
            } else {
                // 当node=null的时候，将节点的值加入集合当中。
                ans.add(stack.pop().val);
            }
        }

        return ans;
    }

 

Mirrors遍历

 public List<Integer> preorderTraversal(TreeNode root) {
        // 存储最终答案的集合。
        List<Integer> ans = new LinkedList<>();

        // Mirrors遍历使用的指针。
        TreeNode p1 = root, p2 = null;
        
        // Mirrors遍历
        while (null != p1) {
            p2 = p1.left;
            if (null == p2) {
                // 左子树为空，将结果加入集合，指针直接向右子树移动。
                ans.add(p1.val);
            } else {
                // 左子树不为空，找到左子树的最右节点，判断该节点的右节点。
                // 寻找最有节点。
                while (null != p2.right && p1 != p2.right) {
                    p2 = p2.right;
                }

                // 如果最右节点的右节点是空。
                if (null == p2.right) {
                    // 进行连接，将最右节点的右节点设置为当前节点。
                    p2.right = p1;
                    // 节点加入集合。
                    ans.add(p1.val);
                    // 当前节点往左移动。
                    p1 = p1.left;
                    continue;
                } else {
                    // 最右节点的右节点不是null，指针向有移动，断开连接。
                    p2.right = null;
                }
            }

            p1 = p1.right;
        }

        return ans;
    }

 

中序遍历

leetcode中序遍历

---

 

递归遍历

public List<Integer> inorderTraversal(TreeNode root) {
        // 存放节点的值。
        List<Integer> ans = new LinkedList<>();
        traversal(ans, root);
        return ans;

    }
    private void traversal(List<Integer> ans, TreeNode root) {
        // 递归结束条件。
        if (null == root) {
            return;
        }

        // 遍历左子树。
        traversal(ans, root.left);
        // 加入节点的值。
        ans.add(root.val);
        // 遍历右子树。
        traversal(ans, root.right);
    }

迭代遍历

第一种方式

 public List<Integer> inorderTraversal(TreeNode root) {
        // 存放结果的集合。
        List<Integer> ans = new LinkedList<>();
        // 遍历使用的栈
        Deque<TreeNode> stack = new LinkedList<>();

        // 中序遍历
        while (!stack.isEmpty() || null != root) {
            // 加入左节点。
            while (null != root) {
                stack.push(root);
                root = root.left;
            }

            // 加入节点。
            root = stack.pop();
            // 将当前节点加入集合。
            ans.add(root.val);
            // 遍历右子树。
            root = root.right;
        }

        return ans;
    }

第二种方式

public List<Integer> inorderTraversal(TreeNode root) {
        // 存放结果的集合。
        List<Integer> ans = new LinkedList<>();

        // 二叉树为空。
        if (null == root) {
            return ans;
        }

        // 遍历二叉树使用的栈。
        Deque<TreeNode> stack = new LinkedList<>();
        stack.push(root);

        // 中序遍历。
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            if (null != node) {
                // 压入右节点。
                if (null != node.right) {
                    stack.push(node.right);
                }

                // 压入当前节点。
                stack.push(node);
                // 压入null值作为分隔符。
                stack.push(null);

                // 压入左节点。
                if (null != node.left) {
                    stack.push(node.left);
                }
            } else {
                // 将节点加入集合。
                ans.add(stack.pop().val);
            }
        }

        return ans;
    }

 Mirrors遍历

 public List<Integer> inorderTraversal(TreeNode root) {
        // 存储答案的集合.
        List<Integer> ans = new LinkedList<>();

        // Mirrors遍历需要的指针
        TreeNode p1 = root, p2 = null;
        // Mirrors遍历
        while (null != p1) {
            p2 = p1.left;
            if (null == p2) {
                // 左子树为空。
                // 将节点加入集合。
                ans.add(p1.val);
            } else {
                // 左子树不为空，寻找中序前驱节点。
                while (null != p2.right && p1 != p2.right) {
                    p2 = p2.right;
                }

                if (null == p2.right) {
                    // 前驱节点的右节点为空，将当前节点设置为前驱节点的右节点。
                    p2.right = p1;
                    // 节点向左移动。
                    p1 = p1.left;
                    continue;
                } else {
                    // 前驱节点的右节点不为空，说明左子树已经遍历完成。
                    // 将当前节点加入集合。
                    ans.add(p1.val);
                    // 将前驱节点的右子树设置为null。
                    p2.right = null;
                }
            }

            p1 = p1.right;
        }

        return ans;
    }

 

后序遍历

leetcode后序遍历

---

递归遍历

public List<Integer> postorderTraversal(TreeNode root) {
        // 存储结果的集合。
        List<Integer> ans = new LinkedList<>();
        traversal(ans, root);
        return ans;
    }

    private void traversal(List<Integer> ans, TreeNode root) {
        // 递归的结束条件。
        if (null == root) {
            return;
        }

        // 遍历左子树
        traversal(ans, root.left);
        // 遍历右子树
        traversal(ans, root.right);
        // 遍历根节点。
        ans.add(root.val);
    }

迭代遍历

第一种方式

 public List<Integer> postorderTraversal(TreeNode root) {
        // 存储结果的集合。
        List<Integer> ans = new LinkedList<>();

        // 遍历需要的栈。
        Deque<TreeNode> stack = new LinkedList<>();

        // 进行后序遍历。
        while (!stack.isEmpty() || null != root) {
            while (null != root) {
                stack.push(root);
                root = root.left;
            }

            root = stack.peek();
            if (null != root) {
                // 当前已经遍历完了左子树。
                // 压入一个null作为标记。
                stack.push(null);
                // 不为空。
                root = root.right;
            } else {
                // 为空，代表当前节点右子树已经遍历完成。
                stack.pop();
                ans.add(stack.pop().val);
                root = null;
            }
        }

        return ans;
    }

第二种方式

 public List<Integer> postorderTraversal(TreeNode root) {
        // 存储结果的集合。
        List<Integer> ans = new LinkedList<>();

        // 二叉树为空。
        if (null == root) {
            return ans;
        }

        // 遍历二叉树使用的栈。
        Deque<TreeNode> stack = new LinkedList<>();
        stack.push(root);
        // 进行后序遍历。
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            if (null != node) {
                // 压入根节点。
                stack.push(node);
                // 压入null作为当前节点已经访问过了。
                stack.push(null);

                // 压入右节点。
                if (null != node.right) {
                    stack.push(node.right);
                }
                // 压入左节点。            
                if (null != node.left) {
                    stack.push(node.left);
                }
            } else {
                // 如果为空，说明当前节点已经遍历完成。
                ans.add(stack.pop().val);
            }
        }

        return ans;
    }

Mirrors遍历

 

 public List<Integer> postorderTraversal(TreeNode root) {
        // 存储结果的集合。
        List<Integer> ans = new LinkedList<>();

        // 为了遍历，常见一个虚拟节点。
        TreeNode dummy = new TreeNode(0, root, null);
        // Mirrors遍历需要的指针。        
        TreeNode p1 = dummy, p2 = null;

        // 进行Mirrors遍历。
        while (null != p1) {
            p2 = p1.left;
            // 当前节点的左子树为空的时候，直接向右子树移动。
            if (null != p2) {
                // 当前节点的左子树不为空。
                // 寻找前驱节点。
                while (null != p2.right && p1 != p2.right) {
                    p2 = p2.right;
                }

                if (null == p2.right) {
                    // 前驱节点的右子树为空，进行连接。
                    p2.right = p1;
                    // 指针向左移动。
                    p1 = p1.left;
                    continue;
                } else {
                    // 前驱节点的右子树不为空，说明当前节点的已经访问完成了。
                    // 断开连接。
                    p2.right = null;
                    // 将从p1的左节点一直到前驱节点全部加入到集合当中。
                    addNode(ans, p1.left);
                }
            }

            p1 = p1.right;
        }

        // 销毁哑节点。
        dummy.left = null;
        return ans;
    }

    private void addNode(List<Integer> ans, TreeNode root) {
        // 获取集合当中已有元素的个数。
        int size = ans.size();
        // 倒序插入节点。
        while (null != root) {
            ans.add(size, root.val);
            root = root.right;
        }
    }

note:后序遍历的Mirrors遍历，如果不使用容器，需要反转右子树。这样作者没有想到更完善的方法，如果有更好的方法，欢迎告诉作者。

 

作者目前只是一个自学编程的小白， 如果您发现文章又任何错误的地方，欢迎指出。