二叉樹預購和後續訂單遍歷是否一致？

Question

是否存在這種情況爲真的二叉樹？

我不這麼認爲，除非二叉樹只包含一個根節點。

Answer 1

你是對的：假設根節點至少有一個孩子。

在預先遍歷中，首先處理根節點。孩子追趕它。這很容易在僞代碼中看到：

preorder(node) 
    if node == null then return 
    print node.value 
    preorder(node.left) 
    preorder(node.right) 

在後序遍歷中，根節點是要處理的最後一個，而子節點是第一個;再次看代碼：

postorder(node) 
    if node == null then return 
    postorder(node.left) 
    postorder(node.right) 
    print node.value 

（從Wikipedia的僞代碼）。

總之，如果二叉樹有多個節點，遍歷必然是不同的。