DAY14|二叉树的遍历

二叉树的遍历

文档讲解：二叉树的遍历

状态：掌握二叉树的，前中后序遍历方式，最主要的是理解为什么要这么处理

为什么需要树？

• 数组的查找效率高，但是插入效率低。
• 链表的插入效率高，查找效率低。

需要一种数据结构来平衡查找与插入效率，使得查找速度和插入速度都能得到提升，因此有了树这种数据结构。

满二叉树

如果该二叉树的所有叶子节点都在最后一层，并且结点总数= 2^n -1 , n为层数，则我们称为满二叉树。

完全二叉树

如果该二叉树的所有叶子节点都在最后一层或者倒数第二层，而且最后一层的叶子节点在左边连续，倒数第二层的叶子节点在右边连续，我们称为完全二叉树

二叉树的遍历

前序遍历

先遍历父节点，再遍历左子节点，最后遍历右子节点

中序遍历

先遍历左子节点，再遍历父节点，最后遍历右子节点

后序遍历

先遍历左子节点，再遍历右子节点，最后遍历父节点

可以看出，前中后的区别在于父节点遍历的时机

如下案例：

代码

144.递归-前序遍历

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new LinkedList<>();
        preTraverse(root, result);
        return result;
    }

  	//前序遍历
    public void preTraverse(TreeNode node, List<Integer> result) {
        if (node == null) {
            return;
        }
        result.add(node.val);
        preTraverse(node.left, result);
        preTraverse(node.right, result);
    }
}

迭代法-前序遍历

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new LinkedList<>();
        Stack<TreeNode> tempStack = new Stack<>();
        tempStack.push(root);
        while (!tempStack.isEmpty()) {
            TreeNode node = tempStack.pop();
            if (node != null) {
                result.add(node.val);
            } else {
                continue;
            }
            tempStack.push(node.right);
            tempStack.push(node.left);
        }
        return result;
    }
}

145.递归-后序遍历

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new LinkedList<>();
        middleTraverse(root, result);
        return result;
    }

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

迭代法-后序遍历

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        LinkedList<Integer> result = new LinkedList<>();
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode treeNode = stack.pop();
            if (treeNode != null) {
                result.add(treeNode.val);
            } else {
                continue;
            }
            stack.push(treeNode.left);
            stack.push(treeNode.right);
        }
        Collections.reverse(result);
        return result;
    }
}

94.递归-中序遍历

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new LinkedList<>();
        middleTraverse(root, result);
        return result;
    }

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