LeetCode二叉树的前序、中序、后序遍历（递归实现）

本文用递归算法实现二叉树的前序、中序和后序遍历，提供Java版的基本模板，在模板上稍作修改，即可解决LeetCode144. Binary Tree Preorder Traversal（二叉树前序遍历），94. Binary Tree Inorder Traversal（二叉树中序遍历），145. Binary Tree Postorder Traversal（二叉树后序遍历）。

基本概念

二叉树的遍历是根据访问结点操作发生位置命名：

前序：访问根结点的操作发生在遍历其左右子树之前。

中序：访问根结点的操作发生在遍历其左右子树之中。

后序：访问根结点的操作发生在遍历其左右子树之后。

模板准备

模板比较简单，废话不说了，直接上代码。

二叉树节点定义：

//Definition for a binary tree node.

public class TreeNode {

    int val;

    TreeNode left;

    TreeNode right;

    TreeNode(int x) { val = x; }

}

前序遍历：

public void preOrder(TreeNode node){

    if(node == null){

        return;

    }

    System.out.println(node.val);

    preOrder(node.left);

    preOrder(node.right);

}

中序遍历：

public void inOrder(TreeNode node){

    if(node == null){

        return;

    }

    inOrder(node.left);

    System.out.println(node.val);

    inOrder(node.right);

}

后序遍历：

public void postOrder(TreeNode node){

    if(node == null){

        return;

    }

    postOrder(node.left);

    postOrder(node.right);

    System.out.println(node.val);

}

LeetCode题解

LeetCode上面关于二叉树遍历的问题有：

#	Title
144	Binary Tree Preorder Traversal
94	Binary Tree Inorder Traversal
145	Binary Tree Postorder Traversal

解答以上问题，只需要在遍历模板上稍作修改即可：题目要求返回类型是List，所以只需要在访问元素的时候把元素添加到结果列表中。

144. Binary Tree Preorder Traversal

class Solution {

    public List<Integer> preorderTraversal(TreeNode root) {

        List<Integer> ret =new ArrayList<Integer>();

        preOrder(root,ret);

        return ret;

    }

    public void preOrder(TreeNode node,List<Integer> ret){

        if(node == null){

            return ;

        }

        ret.add(node.val);

        preOrder(node.left,ret);

        preOrder(node.right,ret);

    }

}

94. Binary Tree Inorder Traversal

class Solution {

    public List<Integer> inorderTraversal(TreeNode root) {

        List<Integer> ret = new ArrayList<Integer>();

        inOrder(root,ret);

        return ret;

    }

    public void inOrder(TreeNode node,List<Integer> ret){

        if(node == null){

            return ;

        }

        inOrder(node.left,ret);

        ret.add(node.val);

        inOrder(node.right,ret);

    }

}

145. Binary Tree Postorder Traversal

class Solution {

    public List<Integer> postorderTraversal(TreeNode root) {

        List<Integer> ret =new ArrayList<Integer>();

        postOrder(root,ret);

        return ret;

    }

    public void postOrder(TreeNode node,List<Integer> ret){

        if(node == null){

            return ;

        }

        postOrder(node.left,ret);

        postOrder(node.right,ret);

        ret.add(node.val);

    }

}

总结

二叉树是天然的递归结构，利用此递归结构，可以巧妙地解决许多看似复杂的二叉树问题。

巴特西