题目1描述

给定一个二叉树,返回它的 前序 遍历。

 示例:

输入: [1,null,2,3]  
   1
    \
     2
    /
   3 

输出: [1,2,3]

进阶: 递归算法很简单,你可以通过迭代算法完成吗?

https://leetcode-cn.com/problems/binary-tree-preorder-traversal/

解法1 – 递归算法

递归解法:定义一个函数private void preorder(TreeNode node, List ans),如果node为空则返回,否则将node.val添加到ans中。然后依次递归调用preorder(node.left, ans)访问node的左子树;递归调用preorder(node.right, ans)访问node的右子树。

时间复杂度O(n),空间复杂度O(n)(递归过程中会创建调用栈,实际上还是有额外空间的),其中n为二叉树节点数量。全部代码如下:

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

    private void preorder(TreeNode node, List<Integer> ans) {
        if (node == null)
            return;
        ans.add(node.val);
        preorder(node.left, ans);
        preorder(node.right, ans);
    }
}

解法2 – 迭代算法

我们创建栈stack,首先将跟节点入栈,然后取出栈顶元素node访问,将node.val加入到结果数组ans中。然后,我们将右子树、左子树依次入栈(如果他们不为空)。因为先序遍历需要依次访问跟节点、左子树、右子树,所以我们需要先将右子树入栈,再将左子树入栈。

时间复杂度O(n),空间复杂度O(n)。全部代码如下:

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        if (root == null)
            return ans;
        Stack<TreeNode> stack = new Stack<>();

        stack.push(root);

        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            ans.add(node.val);
            if (node.right != null)
                stack.push(node.right);
            if (node.left != null)
                stack.push(node.left);
        }

        return ans;
    }
}

题目2描述

给定一个二叉树,返回它的中序 遍历。

示例:

输入: [1,null,2,3]
   1
    \
     2
    /
   3

输出: [1,3,2]

进阶: 递归算法很简单,你可以通过迭代算法完成吗?

https://leetcode-cn.com/problems/binary-tree-inorder-traversal/

解法1 – 递归算法

和题目1的递归算法类似,我们只需要调整访问node的顺序,使其先递归访问node的左子树;然后将node.val加入到结果数组;最后递归访问node的右子树即可。

时间复杂度O(n),空间复杂度O(n)。全部代码如下:

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

        inorder(root, ans);

        return ans;
    }

    private void inorder(TreeNode root, List<Integer> ans) {
        if (root == null)
            return;
        inorder(root.left, ans);
        ans.add(root.val);
        inorder(root.right, ans);
    }
}

解法2 – 迭代算法

为了能够将递归算法转化为迭代算法,我们需要模拟调用栈的过程。中序遍历要求最先访问左子树,那我们就创建栈stack,变量node指向当前节点,一直向左下角走,将沿途的节点都加入到stack中,直到走到空节点。当走到空节点时,我们从栈中弹出一个节点并访问,这就是第一个被访问的左子节点。然后我们将node指向node的右子树(node = node.right),继续重复上面的过程。

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

        if (root == null)
            return ans;
        Stack<TreeNode> stack = new Stack<>();

        TreeNode node = root;
        while (!stack.isEmpty() || node != null) {
            if (node != null) { // 向左走到尽头
                stack.push(node);
                node = node.left;
            } else { // 出栈并访问
                node = stack.pop();
                ans.add(node.val);
                node = node.right; // node指向它的右子树,下次循环继续访问
            }
        }

        return ans;
    }
}

上面的描述有点费解,我们画图来表示。

图1 – 中序遍历示例

图1描述了两个中序遍历示例,红色数字表示访问顺序。比较费解的是,为什么当我们访问node完毕后,需要将node指向node的右子树?我们举两个例子来描述非递归中序遍历的过程。图1左半部分,当node(红色数字1)访问完毕后,我们执行node = node.right,然后node的值被置为空。当下次循环我们发现node为空,就会从栈中弹出一个节点赋予node(红色数字2)。然后,我们访问刚刚出栈的node(红色数字2),它是node(红色数字1)的父节点。此时,我们完成了左子树、跟节点的访问,我们再执行node = node.right,然后node会指向红色数字3的节点,下次循环将会把这个节点入栈。下一次出栈,更新node变量(node为红色数字3),然后访问node节点。这时候我们就执行完了整棵树左子树的中序遍历

图1右半部分与左半部分相比,整棵树的左子树少了一个叶子节点。当node(红色数字1)访问完毕后,我们执行node = node.right,此时node指向红色数字2的那个节点。下一次循环,node入栈,然后向左走,使得node为空。再一次循环,因为node为空,我们要出栈一个节点赋予node(红色数字2),然后访问它。这时候我们就执行完了整棵树左子树的中序遍历。因此,node = node.right是从跟节点返回后,为了访问右子树而将右子树入栈。

时间复杂度O(n),空间复杂度O(n)。全部代码如下:

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

        if (root == null)
            return ans;
        Stack<TreeNode> stack = new Stack<>();

        TreeNode node = root;
        while (!stack.isEmpty() || node != null) {
            if (node != null) {
                stack.push(node);
                node = node.left;
            } else {
                node = stack.pop();
                ans.add(node.val);
                node = node.right;
            }
        }

        return ans;
    }
}

题目3描述

给定一个二叉树,返回它的 后序 遍历。

示例:

输入: [1,null,2,3]  
   1
    \
     2
    /
   3 

输出: [3,2,1]

进阶: 递归算法很简单,你可以通过迭代算法完成吗?

解法1 – 递归算法

与前面两种递归解法类似,我们调整递归调用的顺序,将访问节点的操作放在左子树、右子树递归调用之后就能够实现后序遍历的递归算法。全部代码如下:

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

        postorder(root, ans);

        return ans;
    }

    private void postorder(TreeNode root, List<Integer> ans) {
        if(root==null)
            return;
        postorder(root.left, ans);
        postorder(root.right, ans);
        ans.add(root.val);
    }
}

解法2 – 迭代算法

后序遍历的迭代算法实现起来较为复杂,因为涉及到跟节点的两次访问。我们遇到跟节点时不能直接出栈,而是调用peek函数先查看栈顶元素。如果栈顶元素有右子树,我们还需要将右子树入栈,而不是直接访问栈顶元素(否则就成了中序遍历)。此外,我们还需要记录上一次访问的元素,如果上一次访问的元素就是右子树,我们就不要再访问了,否则就会出现跟节点->右子树->跟节点->右子树……循环访问的情况。

图2 – 后续遍历访问次序

我们在图3中绘制了由三个节点组成的满二叉树的访问次序,node记录当前节点,last记录上一次被访问的节点。首先,node指向跟节点,将跟节点入栈,然后node = node.left(1);接下来,左叶子节点入栈,node = node.left(2);接下来,node为空,使用peek访问栈顶元素,发现栈顶元素的右子树为空,将栈顶元素出栈并访问(3),last = node,将node置空,这样我们就完成了左叶子结点的访问

下一次循环发现node为空,使用peek访问栈顶元素(4),发现栈顶元素的右子树不为空,且上一次访问的节点不是该节点,执行node = node.right,下次循环会将右叶子节点入栈(5),然后node = node.left,使得node为空(6)。下次循环发现node为空,调用peek访问栈顶元素,发现栈顶元素右子树为空,将右叶子节点出栈并访问(7),last = node,然后将node置空,这样我们就完成了右叶子节点的访问

下一次循环发现node为空,使用peek访问栈顶元素,发现栈顶元素的右子树不为空,但是栈顶元素的右子树与上一次访问的节点last相同,此时我们知道刚刚已经访问了右子树,现在该访问跟节点了,我们将跟节点出栈并访问(8),然后last = node,将node置空,我们就完成了跟节点的访问。此时栈为空,node为空,整个遍历流程结束。

时间复杂度、空间复杂度和上面两种遍历方式相同,全部代码如下:

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> ans = new LinkedList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode node = root, last = null;

        while (!stack.isEmpty() || node != null) {
            if (node != null) {
                stack.push(node);
                node = node.left;
            } else {
                node = stack.peek();

                if (node.right != null && last != node.right) {
                    node = node.right;
                } else {
                    node = stack.pop();
                    ans.add(node.val);
                    last = node;
                    node = null;
                }
            }
        }

        return ans;
    }
}

解法3 – 迭代算法

上面解法2有些复杂,记忆和实现起来有些难度。我们可以这么想,后序遍历是先序遍历的变形。先序遍历的顺序是跟节点->左子树->右子树,而后续遍历的顺序是左子树->右子树->跟节点。我们修改先序遍历算法,将入栈顺序调整为跟节点->左子树->右子树,这样出栈序列为跟节点->右子树->左子树。然后我们将出栈序列倒叙,得到左子树->右子树->跟节点,这正是我们需要的后序遍历顺序。

该方法的好处是写起来简单,容易记忆。缺点是,需要将出栈顺序逆序才是答案。如果存放结果的容器是LinkedList,那么我们每次将出栈序列都插入第0个位置,遍历后得到的序列就是逆序的。如果存放结果容器是Array,那么add(0, val)将会造成元素移动,会使得总的时间复杂度为O(n^2)。如果我们调用add(val)向数组末尾插入,最后再逆序,那么时间复杂度为O(2*n),还是会比解法2要慢。

全部代码如下:

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> ans = new LinkedList<>();
        if (root == null)
            return ans;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode node = root;
        stack.push(node);

        while (!stack.isEmpty()) {
            node = stack.pop();
            ans.add(0, node.val); // 总是插入到第0位置,这样最终结果为访问顺序的逆序。
            if (node.left != null)
                stack.push(node.left);
            if (node.right != null)
                stack.push(node.right);
        }

        return ans;
    }
}
pwrliang Algorithms, DFS, Tree ,

Leave a Reply

Your email address will not be published. Required fields are marked *