二叉树遍历最好的讲解

  • Z时代
  • 2024-01-10
  • 分类：综合

编程

摘自：https://www.jianshu.com/p/9f148caf2535

在网上看了众多版本，这里的讲解是最好的，而且其非递归的后序遍历思路也是最妙的。

前
while(node != null || !stack.isEmpty()) {
    if(node != null) {
        stack.push(node);
        list.add(node.val);
        node = node.left;
    }else {
        node = stack.pop();
        node = node.right;
    }
}
中
while(node!=null || !stack.isEmpty()) {
    if(node != null) {
        stack.push(node);
        node = node.left;
    }else {
        node = stack.pop();
        list.add(node.val);
        node = node.right;
    }
}
后
while(node != null || !stack.isEmpty()) {
    if(node != null) {
        stack.push(node);
        list.add(0, node.val);
        node = node.right;
    }else {
        node = stack.pop();
        node = node.left;
    }
}

后序遍历的输出顺序是左、右、根，当我们采用先序遍历的方法，但是先遍历右子树，实现的效果是根、右、左，刚好和后序遍历的结果想法，所以我们通过add(0, node)的方式将顺序反序，达到我们想要的效果。

 

层次遍历可以参考这个：

 public static void level(BTNode node) {
        ArrayDeque<BTNode> queue = new ArrayDeque<>(20);
        //首先将根节点加入栈中
        queue.add(node);
        //遍历二叉树
        while (!queue.isEmpty()) {
            BTNode tempNode = queue.poll();
            System.out.print(tempNode.data + " ");
            if(tempNode.leftChild != null){
                queue.add(tempNode.leftChild);
            }
            if(tempNode.rightChild != null){
                queue.add(tempNode.rightChild);
            }
        }
    }

 

以上是 二叉树遍历最好的讲解 的全部内容， 来源链接： utcz.com/z/516284.html

回到顶部