第144、94、145、102题 二叉树遍历

二叉树遍历分为四种遍历，前序遍历、中序遍历、后序遍历和层序遍历。在本文中，将使用递归的的方法来对四类遍历进行实现。

144. 前序遍历

 144. 题目描述：

给你二叉树的根节点 root ，返回它节点值的 前序 遍历。

题目给出了树结点的预定义：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */

144. 题目解析：

 采用前序方式进行遍历，首先我们要知道前序遍历的规则，例如存在如上图所示的二叉树，我们采用根结点>左结点>右结点的优先级顺序进行遍历，对应输出应该为：3、9、20、15、7。也就是说，我们在输出一个结点后，下一步应该是去输出该结点的左结点，若其左结点不存在子结点时，再去输出其右结点。代码如下：

class Solution {
    List<Integer> list;
    public List<Integer> preorderTraversal(TreeNode root) {
        list  = new ArrayList<>();
        QXBL(root);
        return list;
    }

    void QXBL(TreeNode root){
        if(root == null)return;
        list.add(root.val);
        QXBL(root.left);
        QXBL(root.right);
    }
}

执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户

内存消耗：40 MB, 在所有 Java 提交中击败了7.13%的用户

94. 中序遍历

94. 题目描述：

给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。

题目给出了树结点的预定义：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */

94. 题目解析：

 采用中序方式进行遍历，首先我们要知道中序遍历的规则，例如存在如上图所示的二叉树，我们采用左结点>根结点>右结点的优先级顺序进行遍历，对应输出应该为：9、3、15、20、7。按照访问左子树——根节点——右子树的方式遍历这棵树，而在访问左子树或者右子树的时候，我们按照同样的方式遍历，直到遍历完整棵树。因此整个遍历过程天然具有递归的性质，我们可以直接用递归函数来模拟这一过程。代码如下：

class Solution {
    List<Integer> list;
    public List<Integer> inorderTraversal(TreeNode root) {
        list = new ArrayList<Integer>();
        ZXBL(root);
        return list;
    }

    void ZXBL(TreeNode root){
        if(root == null)return;
        ZXBL(root.left);
        list.add(root.val);
        ZXBL(root.right);
    }
}

执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户

内存消耗：39.8 MB, 在所有 Java 提交中击败了36.75%的用户

145. 后序遍历

145. 题目描述：

给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。

题目给出了树结点的预定义：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */

145. 题目解析：

 采用后序方式进行遍历，首先我们要知道后序遍历的规则，例如存在如上图所示的二叉树，我们采用左结点>右结点>根结点的优先级顺序进行遍历，对应输出应该为：9、20、15、7、3。也就是说，按照访问左子树——右子树——根节点的方式遍历这棵树，而在访问左子树或者右子树的时候，我们按照同样的方式遍历，直到遍历完整棵树。因此整个遍历过程天然具有递归的性质，我们可以直接用递归函数来模拟这一过程。代码如下：

class Solution {
    List<Integer> list;
    public List<Integer> postorderTraversal(TreeNode root) {
        list = new ArrayList<Integer>();
        ZXBL(root);
        return list;
    }

    void ZXBL(TreeNode root){
        if(root == null)return;
        ZXBL(root.left);
        ZXBL(root.right);
        list.add(root.val);
    }
}

执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户

内存消耗：39.5 MB, 在所有 Java 提交中击败了67.60%的用户

102. 层序遍历

102. 题目描述：

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。（即逐层地，从左到右访问所有节点）。

题目给出了树结点的预定义：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */

102. 题目解析：

 采用层序方式进行遍历，首先我们要知道层序遍历的规则，例如存在如上图所示的二叉树，我们采取从上到下从左到右，按层级依次输出，对应输出应该为：3、9、20、15、7。代码如下：

class Solution {
    List<List<Integer>> list;
    public List<List<Integer>> levelOrder(TreeNode root) {
        list = new ArrayList<List<Integer>>();
        CXBL(root , 1);
        return list;
    }

    void CXBL(TreeNode root, int depth){
        if(root == null)return;
        List<Integer> temp;
        if(depth>list.size()) temp = new ArrayList<Integer>();
        else temp = list.get(depth-1);
        temp.add(root.val);
        if(depth>list.size()) list.add(temp);
        else list.set(depth-1,temp);
        CXBL(root.left,depth+1);
        CXBL(root.right,depth+1);
    }
}

简单解释一下代码，我们利用depth变量来代表结点所处的层级，我们将结点和对应的层级数传入到我们的层序遍历递归函数中，如果链表list的尺寸小于我们的层级，则我们就new一个链表（temp）出来，否则我们就将该层级对应的链表取出来赋值给temp，然后将val，添加到temp链表中，再将temp添加到list中，或取代对应层级的链表。

执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户

内存消耗：42 MB, 在所有 Java 提交中击败了5.19%的用户

学习总结：

四种遍历方式的遍历顺序：

前序遍历：根->左->右

中序遍历：左->根->右

后序遍历：左->右->根

层序遍历：从上往下，从左往右