树的前中后序深度优先算法（迭代法+递归法）-日记篇

说明：问题来源于

leetcode的前序遍历

leetcode的中序遍历

leetcode的后序遍历

一、深度优先遍历递归法：

1、前序遍历

对于树

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;

    public TreeNode(int val) {
        this.val = val;
    }

    public TreeNode() {
    }

    public TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

树的节点不为空时必须保证其val是有值的情况下，深度优先算法的前序遍历：

public class Solution {
    List<Integer> list = new LinkedList<>();

    public List<Integer> preorderTraversal(TreeNode root) {
        selectGoal(root);
        return list;
    }
    public void selectGoal(TreeNode root){
        if (root == null) return;
        list.add(root.val);
        selectGoal(root.left);
        selectGoal(root.right);
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

如果说树节点的val没有定义，那么便在以上稍作修改：

class TreeNode {
    public Integer val;
    public TreeNode left;
    public TreeNode right;

    public TreeNode(Integer val) {
        this.val = val;
    }

    public TreeNode() {
    }

    public TreeNode(Integer val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
public class Solution {
    List<Integer> list = new LinkedList<>();

    public List<Integer> preorderTraversal(TreeNode root) {
        selectGoal(root);
        return list;
    }
    public void selectGoal(TreeNode root){
        if (root == null) return;
        if (root.val != null) list.add(root.val);
        selectGoal(root.left);
        selectGoal(root.right);
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

2、对于后序遍历：

public class Solution {
    List<Integer> list = new LinkedList<>();
    public List<Integer> postorderTraversal(TreeNode root) {
        selectGoal(root);
        return list;
    }
    public void selectGoal(TreeNode root){
        if (root == null) return;
        selectGoal(root.left);
        selectGoal(root.right);
        list.add(root.val);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

3、对于中序排序:

public class Solution {
    List<Integer> list = new LinkedList<>();
    public List<Integer> inorderTraversal(TreeNode root) {
        selectGoal(root);
        return list;
    }
    private void selectGoal(TreeNode root){
        if (root == null) return;
        selectGoal(root.left);
        list.add(root.val);
        selectGoal(root.right);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

二、迭代法：

1、前序遍历：

public class Solution {
    private List<Integer> list = new LinkedList<>();

    public List<Integer> preorderTraversal(TreeNode root) {
        if (root == null) return list;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()){
            TreeNode treeNode = stack.pop();
            list.add(treeNode.val);
            if (treeNode.right != null) stack.push(treeNode.right);
            if (treeNode.left != null) stack.push(treeNode.left);
        }
        return list;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

2、中序遍历

public class Solution {
    List<Integer> list = new LinkedList<>();
    public List<Integer> inorderTraversal(TreeNode root) {
        if (root == null) return list;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()){
            TreeNode peek = stack.peek();
            if (peek.left == null){
                TreeNode pop = stack.pop();
                list.add(pop.val);
                if (pop.right != null){
                    stack.push(pop.right);
                }
            }else {
                TreeNode pop = peek;
                if (peek.right != null) {
                    pop = stack.pop();
                    stack.push(peek.right);
                    stack.push(pop);
                }
                stack.push(pop.left);
                pop.left = null;
                pop.right = null;
            }
        }
        return list;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

思路：先将root节点放进stack里，通过while循环对树节点进行处理（有一种破坏其“莲藕”的“丝”，毁其“叶”的感觉，对应着下面的②中对于左右孩子砍掉的意思）

然后来一次while循环对stack容器进行非空判断对root的左节点进行判断

• ①如果stack里的出口元素peek（通过pop或者peek获取的树节点）的左树节点为空，那么说明这一层上链表应该放peek.val，再放右树节点的数据。因此需要将peek元素从stack里pop出来。并且对右树节点进行判断，如果该右树节点非空，那么就push到stack。

• ②如果出口元素的左树节点不为空，那么我们需要将peek和peek.left以及peek.right在stack的位置进行排序，肯定是先放peek.right（如果不为空的话），再放peek（要将左树节点和右树节点）砍掉，最后放peek.left。方便链表添加的顺序是“前中后”。

3、后序遍历

class Solution {
    List<Integer> list = new LinkedList<>();
    public List<Integer> postorderTraversal(TreeNode root) {
        if (root == null) return list;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()){
            TreeNode peek = stack.peek();
            if (peek.left == null){//左子树为null时
                if (peek.right == null) {//左子树为null时，且右子树也等于null
                    list.add(peek.val);
                    stack.pop();
                }else {//左子树为null时，且右子树也bu等于null
                    TreeNode right = peek.right;
                    peek.right = null;
                    stack.push(right);
                }
            }else {//左子树bu为null
                if (peek.right != null) {//左子树bu为null，且右子树也bu等于null
                    stack.push(peek.right);
                }
                stack.push(peek.left);
                peek.right = null;
                peek.left = null;
            }
        }
        return list;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

思路和中序遍历的基本一样

整体思想将单个树的节点进行左右树节点判断，因为对于一颗树，假如是peek那么我们想放到链表里的顺序是peek.left的数据,再到peek.right最后到peek.val，这个是后序遍历，那么我们放到栈里的顺序肯定是peek.val，再到peek.right最后才是peek.left。因此肯定进入循环后是先对peek.left进行判断，并且当peek的左右树节点均为null时才可以add到链表里面进行保存。

心得：

以上是xin麒思考并且做出来了，三种迭代法的是通过栈来处理root(中序和后续方法会导致root的结构会被拆解)，放到栈里面，细细看里面的顺序的要求会导致链表保存的结果是怎么样的。看到代码行数有些是可以优化的（也就是改的简洁些），不过不优化可以保留自己思考过的踩过的细节。

当然对于迭代法网上也很多各种类型题的模板，如果是面试的话可能就多数都是找模板就可以了，不适合看上面的。