二叉树（& BST）的前序、中序、后序遍历(递归与迭代)，java BST的构建_bst 中序遍历

这里迭代的写法更新了, 不用看文字, 直接看代码, 可以作为模板, 三个是相互之间通的

关于前序中序后序遍历

比如上图正常的一个满节点，A：根节点、B：左节点、C：右节点，前序顺序是ABC（根节点排最先，然后同级先左后右）；中序顺序是BAC(先左后根最后右）；后序顺序是BCA（先左后右最后根）。
皆是根节点（当前节点）访问的位置来命名，都是用dfs来实现。
前序：根左右
中序：左根右
后序：左根中

其实用递归的思想来理解前序中序后序会比较好。
比如中序：
每到一个新的节点，你都要考虑一个事就是左根右。当前节点是根。
你需要先去找左。（或者说是 遍历左 访问当前 遍历右 这样可能更好理解一些）
如此，面对这样一个二叉树：

前序遍历：ABCDEFGHK

中序遍历：BDCAEHGKF

后序遍历：DCBHKGFEA

java代码实现-递归

前序：

void dfs(TreeNode root) {
    visit(root);
    dfs(root.left);
    dfs(root.right);
}
1
2
3
4
5

中序：

void dfs(TreeNode root) {
    dfs(root.left);
    visit(root);
    dfs(root.right);
}
1
2
3
4
5

后序：

void dfs(TreeNode root) {
    dfs(root.left);
    dfs(root.right);
    visit(root);
}

1
2
3
4
5
6

具体实例：LeetCode144 二叉树的前序遍历
题目详情：给你二叉树的根节点 root ，返回它节点值的 前序 遍历。

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> visited = new LinkedList<>();
        dfs(root,visited);
        return visited;

    }

    public void dfs(TreeNode s, List<Integer> visited){
        if(s==null){
            return;
        }
        visited.add(s.val);
        dfs(s.left,visited);
        dfs(s.right,visited);
        return;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

后序中序类似

java代码实现-迭代

这里迭代实际上也是用栈来模拟递归的思路。
因为实际上递归也是栈的调用。
前序

	public List<Integer> preorderTraversal(TreeNode root) {
        Deque<TreeNode> stack = new LinkedList<>();
        List<Integer> res = new ArrayList<>();
        TreeNode cur = root;
        while(!stack.isEmpty()||cur!=null){
            while(cur!=null){
                res.add(cur.val);
                stack.push(cur);
                cur = cur.left;
            }
            cur = stack.pop().right;
        }
        return res;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

这里用到栈，栈是先进后出。
所以这里用非递归，为了保证前序，先把当前节点加入。中
然后为了保证之后先左后右，所以这里是右先入栈，左后入栈。左 右

而后序的话：
前序遍历为 root -> left -> right，后序遍历为 left -> right -> root。可以修改前序遍历成为 root -> right -> left，那么这个顺序就和后序遍历正好相反。

	//也是用栈, 左右中, 反过来就是中右左, 就是将前序的左右换一下,然后给反一下 中左右->中右左->左右中
	public List<Integer> postorderTraversal(TreeNode root) {
        Deque<TreeNode> stack = new LinkedList<>();
        List<Integer> res = new LinkedList<>();
        TreeNode cur = root;
        while(!stack.isEmpty()||cur!=null){
            while(cur!=null){
                res.add(cur.val);
                stack.push(cur);
                cur = cur.right;
            }
            cur = stack.pop().left;
        }
        Collections.reverse(res);
        return res;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

中序：
这个要麻烦一点，我们每一步都是先将左子节点放入栈中，直到左子节点为空为止，然后再访问，之后再将右子节点放入栈中，如此进行下去。
这里的逻辑是：
先将所有的左进栈
然后访问当前节点
然后再去将右节点进栈（下面代码中右节点并未进栈，是因为如果这里有进栈的话，while顶部还需要出栈，这会大大增加时间复杂度，很没有必要，while底部和顶部用的节点都是同一个节点，所以根本都不需要进栈出栈增加开销。但是理解上可以理解成为进栈）

public List<Integer> inorderTraversal(TreeNode root) {
        Deque<TreeNode> stack = new LinkedList<>();
        List<Integer> res = new LinkedList<>();
        TreeNode cur = root;
        while(!stack.isEmpty()||cur!=null){
            while(cur!=null){
                stack.push(cur);
                cur = cur.left;
            }
            cur = stack.pop();
            res.add(cur.val);
            cur = cur.right;
        }
        return res;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

二叉树的Morris遍历

对于上面的递归遍历实现，其实都是要借助栈的，在java里，由于jvm对于虚拟机栈的限制，会导致当数据量比较庞大时，会栈溢出，所以有些时候，我们需要一个空间复杂度更小的方式来遍历。
这里的morris遍历便是，牺牲了一定的时间复杂度，来换取O(1)的空间复杂度。
由于在递归中，由底层元素返回当上层元素，靠的是栈，这里没有用栈。
而是采取了一个巧妙的方式，即将该点，左子树的最右点指向该点，那么自然而然，就模拟了上层元素出栈的操作，使得能够返回到上层元素。（在morris中这叫设置线索）
然后当访问之后，得删除这个线索，这个也和出栈了的元素访问后被抛弃是一样，能够避免对二叉树的修改。
然后其实在之前的遍历来说，前序对于每个点是遍历一次就打印，而中序是遍历两次打印，后序是遍历三次打印。morris确实是模仿了这个。
在前序中序后序的morris实现中，前两个实现比较简单，我看的没什么问题，也可以用，后序看的有点懵，需要翻转链表，这里先mark一下，应用场景比较上，等到需要的时候再回过头来理解。
先放上两个觉得写的不错的博客，节省时间：
https://blog.csdn.net/wdq347/article/details/8853371
https://blog.csdn.net/pcwl1206/article/details/96977808

对于二叉查找树BST来说，中序遍历得到有序数列

如题
这里BST的特点是，左子树所有值<=根节点值<=右子树所以值

BST（平衡）的创建

平衡在于每次找最中间的，所以能够保证是平衡的（左右子树深度差不超过1）
其实我要构建BST，不保证平衡的，只需在整个区间中间任意选一个值作为该点的值即可，然后左子树便是区间中该点左边的，右子树便是区间中该点右边的。如此逻辑便可以保证根节点大于等于左子树所有值，小于等于右子树所有值，从而构建BST。
而当我每次选值时只考虑最中间的位置，则意味着每一轮，左右子树的个数差距不超过1，那么最终也就会平衡。
（同时，这里使用medium = l + (r-l)/2的目的是为了防止溢出，若用(r+l)/2的话，可能r+l 就溢出了，而r-l是绝不可能溢出的）

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return dfs(nums,0,nums.length-1);

    }

    public TreeNode dfs(int[] nums,int l, int r){
        if(l>r){
            return null;
        }
        int medium = l+(r-l)/2;
        TreeNode node = new TreeNode(nums[medium]);
        node.left = dfs(nums,l,medium-1);
        node.right = dfs(nums,medium+1,r);
        return node;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

参考

https://blog.csdn.net/qq_33243189/article/details/80222629
LeetCode