leetcode

LeetCode 144. Binary Tree Preorder Traversal

Problem

LeetCode 144. Binary Tree Preorder Traversal

1. 题目简述：

给出一颗二叉树，返回其前序遍历的顺序（List形式），且尽量使用非递归的形式。例如：

Input: [1,null,2,3]
1
 \
  2
 /
3
Output: [1,2,3]

2. 算法思路

Stack：

递归的形式很好写，普通的前序遍历，这里不再赘述。问题在于非递归（迭代）的形式怎么办。

我们都知道递归其实就是计算完某节点后不断返回上一级的方法，如果用递归达到同样效果，一般都需要使用栈Stack！

遍历过程：

  1. 如果节点不为空，访问某节点。
  2. 如果某节点存在右子树，压栈；如果存在左子树，压栈（这样弹出时是先左后右）。

Condition Statement：

  1. 注意，第一种解法中这里要先把root给压栈。
  2. 第一种解法中，要注意root为null的情况，所以while判断条件中加了node ！= null的条件，否则会出现NullPointerException。
  3. 第二种解法中，压栈的目的只是为了回溯找右节点，而不是弹出时访问。第一种解法更清晰，是弹出时访问。二者思路有很大不同。

3. 解法

这里提供两种遍历思路：

  1. 遍历时先压右子树，再压左子树。
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        Stack<TreeNode> stack = new Stack<TreeNode>();
        List<Integer> list = new ArrayList<Integer>();
        TreeNode node = root;
        stack.push(node);

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

        return list;
    }
}
  1. 压栈的目的只是为了回溯找右节点，不是压左右子树，而是访问过的节点。
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        Stack<TreeNode> stack = new Stack<TreeNode>();
        List<Integer> list = new ArrayList<Integer>();
        TreeNode node = root;

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

        return list;
    }
}