二叉树-前中后序遍历

今天开始学习树，先从简单的二叉树遍历开始吧。

题目介绍

给定一个二叉树，分别用前序遍历、中序遍历、后序遍历来获取对应节点的值并输出结果。树的结构如下图所示：

二叉树遍历题目.png

先对前中后序遍历知识做个简单介绍：

• 前序遍历，先读取父节点值，然后读取左子树节点值，最后读取右子树节点值。比如上图的结果应为：F->B->A->D->C->E->G->I->H
• 中序遍历，先读取左子树节点值、然后读取父节点值，最后读取右子树节点值。
  比如上图的结果应为：A->B->C->D->E->F->G->H->I
• 后序遍历，先读取左子树节点值，然后读取右子树节点值，最后读取父节点值。
  比如上图的结果应为：A->C->E->D->B->F->H->I->G

实现思路

今天就不上图了，主要说下我的实现主要是基于递归的方式来实现的。而递归代码最重要的是两点：
1、找到递归公式
2、找到终止条件

遍历树的终止条件比较好找，只要是递归到叶子节点就终止递归，然后层层返回。

而递归公式我们可以稍微思考以下，我们定义递归函数为F，节点值几位V，父节点结果P，左子节点记为left，右子节点记为rigth，则可以得到以下公式：
1、前序遍历：F(P) = P.V + F(P.left) + F(P.rigth)；
2、前序遍历：F(P) = F(P.left) + P.V + F(P.rigth)；
3、前序遍历：F(P) = F(P.left) + F(P.rigth) + P.V；

公式出来后，我们就只要找着公式来实现就好了。

实现代码

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class SolutionPreorderTraversal {
    List<Integer> orderList = new ArrayList<>();

    public List<Integer> postorderTraversal(TreeNode root) {
        if (null != root) {
            postorderTraversal(root.left);
            postorderTraversal(root.right);
            orderList.add(root.val);
        }
        return orderList;
    }

    public List<Integer> inorderTraversal(TreeNode root) {
        if (null != root) {
            inorderTraversal(root.left);
            orderList.add(root.val);
            inorderTraversal(root.right);
        }
        return orderList;
    }

    public List<Integer> preorderTraversal(TreeNode root) {
        if (null != root) {
            orderList.add(root.val);
            preorderTraversal(root.left);
            preorderTraversal(root.right);
        }
        return orderList;
    }
}

今天内容还是比较简单的，我们后面再慢慢的深入学习吧。/奸笑