3.二叉树之后序遍历｜Java 刷题打卡-一一网

【Java 刷题打卡】刷题比玩游戏好多了，成就感越来越强，每天坚持刷几道题，每天锻炼30分钟，等8块腹肌,等大厂offer.

$\color{red}{~}$

那就干吧！这个专栏都是刷的题目都是关于二叉树的,我会由浅入深、循序渐进，刷题就是这样需要连续不断的记忆–艾宾浩斯记忆法2121112。二叉树的内容不多，但是都是每个程序员必备的，对了解红黑树、B+树、LSM树都非常有帮助等等

WAL+LSM-tree实现的leveldb和rocksdb

B+ 树的mysql

(HBASE) – LSM-tree的架构把random write转成sequential write，多层的compaction和lookup，存在写放大和读放大

TokuDB索引结构–Fractal Tree

还有更多，值得咱们发掘。

leecode 145. 二叉树的后序遍历

给定一个二叉树，返回它的后序遍历。

示例:

输入: [1,null,2,3]

图片.png
输出: [3,2,1]

首先我们需要了解什么是二叉树的后序遍历：按照访问左子树——右子树——根节点的方式遍历这棵树，而在访问左子树或者右子树的时候，我们按照同样的方式遍历，直到遍历完整棵树。因此整个遍历过程天然具有递归的性质，我们可以直接用递归函数来模拟这一过程。

参考代码

定义一颗树

class TreeNode {
    int val;          // 头结点
    TreeNode left;    // 左子树
    TreeNode right;   // 右子树

    TreeNode(int x) {
        val = x;
    }
}


// 测试方法
 public static void main(String[] args) {
        TreeNode treeNode = new TreeNode(1);
        treeNode.left = new TreeNode(2);
        treeNode.right = new TreeNode(3);
        System.out.println("x序遍历结果 = " + preorderTraversal(treeNode));
}        
复制代码

JAVA语言版 递归

直接怼到最下面的左节点，如果为null,走postorder(node.Right),如果在右节点还有左节点就继续走左节点，直到到最下面的左节点，走第三步，将左节点怼进数组里。
return到右节点，怼进数组
将根节点怼进数组。

   List<Integer> postorderTraversalList = new LinkedList<>();
    public List<Integer> postorderTraversal(TreeNode root) {
        if(root == null)
            return ans;
        postorderTraversal(root.left);
        postorderTraversal(root.right);
        postorderTraversalList.add(root.val);
        return ans;
    }

复制代码

JAVA语言版 迭代栈：先进后出

定义一个栈stk，栈存的就是一棵树

1.先将根节点怼进数组,遍历把左子树全部怼进栈，知道最下面的左节点。

2.将最后进入栈的节点弹出来

3.弹出的节点，如果左节点不为空或者右节点不为空，就继续入栈

4.如果为空，说明这个根节点就是左节点或者右节点，因为左节点先出栈，所以把左节点怼进数组，在怼右节点，直到最后一个根节点。

 public static  List<Integer> inorderTraversal2(TreeNode root) {
        //
        List<Integer> list = new ArrayList<>();
        if (root == null) {
            return list;
        }
        Stack<TreeNode> s = new Stack<>();
        s.push(root);

        while( !s.isEmpty() ) {
            TreeNode node = s.pop(); // 1.出栈root
            if(node.left != null) {
                s.push(node.left); // 2.进栈 2,null,null
            }

            if(node.right != null) {
                s.push(node.right); // 3. 进栈 3,null,null
            }

            list.add(0, node.val); // 从最后插入依次插入 1 3 2 打印出来就是2 1 3
        }
        return list;
    }
复制代码