0823537572fc12221677b34b2ceed3fa
树的后序遍历的两种实现

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

什么是后序遍历

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

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

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

递归

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

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

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

  方法实现

 private static void function(TreeNode head){
        if(head == null){
            return;
        }
        function(head.left);
        function(head.right);
        System.out.println(head.val);
    }

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

循环

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

    private static void function(TreeNode head) {
        if (head == null) {
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        Stack<TreeNode> repeatStack = new Stack<>();
        TreeNode cur = head;
        pushLeftNode(stack, cur);
        while (!stack.empty()) {
            cur = stack.peek();
            if (!repeatStack.empty() && repeatStack.peek() == cur) {
                repeatStack.pop();
                stack.pop();
                System.out.println(cur.val);
            } else {
                if (cur.right != null) {
                    repeatStack.push(cur);
                    pushLeftNode(stack, cur.right);
                } else {
                    cur = stack.pop();
                    System.out.println(cur.val);
                }
            }
        }
    }

    private static void pushLeftNode(Stack<TreeNode> stack, TreeNode node) {
        stack.push(node);
        while (node.left != null) {
            stack.push(node.left);
            node = node.left;
        }
    }

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

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

private static void function(TreeNode head) {
        if (head == null) {
            return;
        }
        Stack<TreeNode> stack1 = new Stack<>();
        Stack<TreeNode> stack2 = new Stack<>();
        stack1.push(head);
        while (!stack1.empty()) {
            TreeNode cur = stack1.pop();
            stack2.push(cur);
            if(cur.left != null){
                stack1.push(cur.left);
            }
            if(cur.right != null){
                stack1.push(cur.right);
            }
        }

        while(!stack2.empty()){
            System.out.println(stack2.pop().val);
        }
    }
© 著作权归作者所有
这个作品真棒,我要支持一下!
一个坚持原创的小专栏。分享编程知识,提升工作效率,致力于通过简单的语言,把编程这点事讲清楚。涵盖内容:java、设...
0条评论
top Created with Sketch.