94、144、145、二叉树的前、中、后序遍历

leetcode链接：

144. 二叉树的前序遍历
94. 二叉树的中序遍历
145. 二叉树的后序遍历

递归求解

前序遍历

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

        recur(root, result);

        return result;
    }

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

结果

解答成功:
执行耗时:0 ms,击败了100.00% 的Java用户
内存消耗:39.9 MB,击败了12.45% 的Java用户

中序遍历

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

        recur(root, result);

        return result;
    }

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

结果

解答成功:
执行耗时:0 ms,击败了100.00% 的Java用户
内存消耗:39.5 MB,击败了87.74% 的Java用户

后序遍历

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

        recur(root, result);

        return result;
    }

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

结果

解答成功:
执行耗时:0 ms,击败了100.00% 的Java用户
内存消耗:39.8 MB,击败了31.17% 的Java用户

总结：

前、中、后序在实现上的区别：

recur(root.left, result);  // 左子树  
result.add(root.val);      // 中节点  
recur(root.right, result); // 右子树

前序代表 中节点 在 前面
中序代表 中节点 在 中间， 上方代码为中序优先搜索
后序代表 中节点 在 后面

迭代法

前序遍历

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        Deque<TreeNode> deque = new LinkedList<>();

        if (root != null) {
            deque.push(root);
        }

        while (!deque.isEmpty()) {
            TreeNode poll = deque.poll();
            result.add(poll.val);
            if (poll.right != null) {
                deque.push(poll.right);
            }
            if (poll.left != null) {
                deque.push(poll.left);
            }
        }
        
        return result;
    }
}

结果

解答成功:
执行耗时:0 ms,击败了100.00% 的Java用户
内存消耗:39.6 MB,击败了73.75% 的Java用户

中序遍历

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

        while (root != null) {
            deque.push(root);
            root = root.left;
        }

        while (!deque.isEmpty()) {
            // 当二叉数的右侧
            while (deque.peek() != null && deque.peek().right == null) {
                TreeNode poll = deque.poll();
                result.add(poll.val);
            }
            // 当栈是空的时候，意味着所有的节点都被弹出栈，遍历挖成
            if (deque.isEmpty()) {
                break;
            }
            // 弹出中间节点
            TreeNode poll = deque.poll();
            result.add(poll.val);

            poll = poll.right;
            while (poll != null) {
                deque.push(poll);
                poll = poll.left;
            }
        }
        
        return result;
    }
}

结果

解答成功:
执行耗时:0 ms,击败了100.00% 的Java用户
内存消耗:39.5 MB,击败了88.16% 的Java用户

后序遍历

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        Deque<TreeNode> deque = new LinkedList<>();

        if (root != null) {
            deque.push(root);
        }

        while (!deque.isEmpty()) {
            TreeNode poll = deque.poll();
            result.add(poll.val);
            if (poll.left != null) {
                deque.push(poll.left);
            }
            if (poll.right != null) {
                deque.push(poll.right);
            }
        }

        Collections.reverse(result);
        return result;
    }
}

结果

解答成功:
执行耗时:0 ms,击败了100.00% 的Java用户
内存消耗:39.4 MB,击败了95.54% 的Java用户