【LeetCode】5 二叉树的各种非递归遍历

1. 非递归实现二叉树的前序遍历

  1. Binary Tree Preorder Traversal (Medium)

Leetcode / 力扣

public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> ret = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        if (node == null) continue;
        ret.add(node.val);
        stack.push(node.right);  // 先右后左,保证左子树先遍历
        stack.push(node.left);
    }
    return ret;
}Copy to clipboardErrorCopied

2. 非递归实现二叉树的后序遍历

  1. Binary Tree Postorder Traversal (Medium)

Leetcode / 力扣

前序遍历为 root -> left -> right,后序遍历为 left -> right -> root。可以修改前序遍历成为 root -> right -> left,那么这个顺序就和后序遍历正好相反。

public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> ret = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        if (node == null) continue;
        ret.add(node.val);
        stack.push(node.left);
        stack.push(node.right);
    }
    Collections.reverse(ret);
    return ret;
}Copy to clipboardErrorCopied

3. 非递归实现二叉树的中序遍历

  1. Binary Tree Inorder Traversal (Medium)

Leetcode / 力扣

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> ret = new ArrayList<>();
    if (root == null) return ret;
    Stack<TreeNode> stack = new Stack<>();
    TreeNode cur = root;
    while (cur != null || !stack.isEmpty()) {
        while (cur != null) {
            stack.push(cur);
            cur = cur.left;
        }
        TreeNode node = stack.pop();
        ret.add(node.val);
        cur = node.right;
    }
    return ret;
}

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×