亲宝软件园·资讯

展开

树的后序遍历的两种实现

进击的李同学 人气:1

今天介绍一下树的后序遍历

什么是后序遍历

  所谓遍历就是将集合中的所有元素都访问一遍,由于树是一种非线性结构,所以它的遍历方式有很多种:

  • 前序遍历 :根左右
  • 中序遍历 :左根右
  • 后序遍历 :左右根
  • 按层遍历 :逐层访问

  接下来我们用动图的方式,看一下树的后序遍历过程:

递归

  我们将动图翻译成代码,就得到了递归的实现方法
  定义树

1class TreeNode{
2    public TreeNode left;
3    public TreeNode right;
4    public int val;
5
6    public TreeNode(int val){
7        this.val = val;
8    }
9}

  方法实现

1 private static void function(TreeNode head){
2        if(head == null){
3            return;
4        }
5        function(head.left);
6        function(head.right);
7        System.out.println(head.val);
8    }

  可以看到递归的方法非常的简单,甚至看一遍就可以记住了,通常这道题到这为止就算做完了,但是你真的理解这段代码吗?或者说如果不用递归,你可以用循环的方式实现这道题吗?

循环

  任何用递归做的题,我们用循环的方式都可以解决。解决的思路大体相同,用代码实现递归的调用栈,我们依然要对照着图示来看,首先我们将树的所有左节点入栈,然后出栈,去遍历它的右节点,将右节点入栈,以此重复上述的过程。具体代码如下(推荐使用方法二,可大概看一下,直接去看方法二):

 1    private static void function(TreeNode head) {
2        if (head == null) {
3            return;
4        }
5        Stack<TreeNode> stack = new Stack<>();
6        Stack<TreeNode> repeatStack = new Stack<>();
7        TreeNode cur = head;
8        pushLeftNode(stack, cur);
9        while (!stack.empty()) {
10            cur = stack.peek();
11            if (!repeatStack.empty() && repeatStack.peek() == cur) {
12                repeatStack.pop();
13                stack.pop();
14                System.out.println(cur.val);
15            } else {
16                if (cur.right != null) {
17                    repeatStack.push(cur);
18                    pushLeftNode(stack, cur.right);
19                } else {
20                    cur = stack.pop();
21                    System.out.println(cur.val);
22                }
23            }
24        }
25    }
26
27    private static void pushLeftNode(Stack<TreeNode> stack, TreeNode node) {
28        stack.push(node);
29        while (node.left != null) {
30            stack.push(node.left);
31            node = node.left;
32        }
33    }

  这种做法比较符合直觉,我们模拟出了一个调用栈,然后借助另一个repeatStack,用来过滤遍历过的元素,防止元素重复遍历的过程。


  还有其他的循环方法,我们可以对方法一的stack进行拆分,拆分出的2个栈,一个用来存储结果,一个用来计算。

 

 1private static void function(TreeNode head) {
2        if (head == null) {
3            return;
4        }
5        Stack<TreeNode> stack1 = new Stack<>();
6        Stack<TreeNode> stack2 = new Stack<>();
7        stack1.push(head);
8        while (!stack1.empty()) {
9            TreeNode cur = stack1.pop();
10            stack2.push(cur);
11            if(cur.left != null){
12                stack1.push(cur.left);
13            }
14            if(cur.right != null){
15                stack1.push(cur.right);
16            }
17        }
18
19        while(!stack2.empty()){
20            System.out.println(stack2.pop().val);
21        }
22    }

加载全部内容

相关教程
猜你喜欢
用户评论