SCL让你1分钟学会-非递归中根遍历二叉树 数据结构二叉树javapython非递归

题目

题目：非递归中根遍历二叉树，树结构如下：

 

遍历结果：20 30 40 50 80 100 120

猜想

非递归先根遍历使用栈是可以的，中根也可以吧？

简化

1.这棵树太复杂了，简单一点更容易理解.于是

 

打印结果：30 50  100。

打印这样的结果，需要50进栈，30进栈，30出栈，50出栈，100进栈再出栈

落实一下代码逻辑

根节点50进栈，左孩子30进栈，左子树30没有左孩子，30弹栈

栈不为空，50弹栈

可是100如何进栈呢？应该是50弹栈的时候，检查是否右孩子，如果有右孩子，将右孩子压栈

 

弹栈时，检查是否存在右孩子，如果有右孩子，将右孩子压栈。我们可以试试给30增加一个右孩子，比如下图：

我们再试试30弹栈的同时，将40压栈是否合适？

这个方法，可以耶，上代码，Python版本

 

class Solution(object):
    """
        50
       /  \
     30   100
    / \   / \
   20 40 80 120       
    """
    def midOrderNoRecursion(self, root):
        if not root:
            return
        stack = list()
        cur_node = root
        while stack or cur_node:
            if cur_node:
                stack.append(cur_node)
            if cur_node and cur_node.left:
                cur_node = cur_node.left
            else:
                node = stack.pop()
                print(node.val)
                if node.right:
                    cur_node = node.right
                else:
                    cur_node = None

Java版本

 

public void midOrderNoRecursion(TreeNode root) {
        if (root == null) {
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode curNode = root;
        while (!stack.isEmpty() || curNode != null) {
            if (curNode != null) {
                stack.add(curNode);
            }
            if (curNode != null && curNode.left != null) {
                curNode = curNode.left;
            } else {
                TreeNode node = stack.pop();
                System.out.println(node.val);
                if (node.right != null) {
                    curNode = node.right;
                } else {
                    curNode = null;
                }
            }
        }
    }

 

关注源代码清单，技术人的学习清单