递归遍历144. 二叉树的前序遍历|94. 二叉树的序遍历|145. 二叉树的后序遍历

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

一、二叉树理论

二叉树遍历方式：

深度优先遍历：前序遍历、中序遍历、后序遍历（递归法，迭代法）

广度优先遍历：层次遍历（迭代法）

二叉树种类：

1. 满二叉树：如果一棵二叉树只有度为0的结点和度为2的结点，并且度为0的结点在同一层上，则这棵二叉树为满二叉树。

2. 完全二叉树：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2^(h-1) 个节点。

3. 二叉搜索树：前面介绍的树，都没有数值的，而二叉搜索树是有数值的了，二叉搜索树是一个有序树。 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为二叉排序树。

4. 平衡二叉搜索树：又被称为AVL（Adelson-Velsky and Landis）树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

二叉树的存储方式：二叉树可以链式存储，也可以顺序存储。 链式存储方式就用指针， 顺序存储的方式就是用数组。 数组方式：如果父节点的数组下标是 i，那么它的左孩子就是 i * 2 1，右孩子就是 i * 2 2。

二叉树的定义：

//二叉树定义
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;
    }
}

二、递归遍历

递归算法的三个要素 ：

1. 确定递归函数的参数和返回值： 确定哪些参数是递归的过程中需要处理的，那么就在递归函数里加上这个参数， 并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。
2. 确定终止条件： 写完了递归算法, 运行的时候，经常会遇到栈溢出的错误，就是没写终止条件或者终止条件写的不对，操作系统也是用一个栈的结构来保存每一层递归的信息，如果递归没有终止，操作系统的内存栈必然就会溢出。
3. 确定单层递归的逻辑： 确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。

二叉树的前序遍历：144. 二叉树的前序遍历 - 力扣（LeetCode）

class Solution {
	//前序遍历
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list1 = new ArrayList<Integer>();
        preorder(root,list1);
        return list1;
    }
    public void preorder(TreeNode root, List list){
        if(root == null) return;
        list.add(root.val);
        preorder(root.left, list);
        preorder(root.right,list);
    }
}

二叉树的中序遍历：94. 二叉树的中序遍历 - 力扣（LeetCode）

class Solution {
    //中序遍历
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list2 = new ArrayList<Integer>();
        inorder(root,list2);
        return list2;
    }
    public void inorder(TreeNode root, List list){
        if(root == null) return;
        inorder(root.left, list);
        list.add(root.val);
        inorder(root.right,list);
    }
}

二叉树的后序遍历：145. 二叉树的后序遍历 - 力扣（LeetCode）

class Solution {
    //后序遍历
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list3 = new ArrayList<Integer>();
        postorder(root,list3);
        return list3;
    }
    public void postorder(TreeNode root, List list){
        if(root == null) return;
        postorder(root.left, list);
        postorder(root.right,list);
        list.add(root.val);
    }
}

这篇好文章是转载于：学新通技术网