二叉树的遍历

扩展练习

二叉树的基本概念

在计算机科学中，二叉树是每个结点最多有两个子树的有序树。通常根的子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用作二叉查找树和二叉堆或是二叉排序树。二叉树的每个结点至多只有二棵子树(不存在出度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。（二叉树）

二叉树的遍历

一棵非空的二叉树由根结点及左、右子树这三个基本部分组成。因此，在任一给定结点上，可以按某种次序执行三个操作：
⑴访问结点本身（N），
⑵遍历该结点的左子树（L），
⑶遍历该结点的右子树（R）。
以上三种操作有六种执行次序：
NLR、LNR、LRN、NRL、RNL、RLN。
注意：
前三种次序与后三种次序对称，故只讨论先左后右的前三种次序。
遍历命名
根据访问结点操作发生位置命名：
① NLR：前序遍历(PreorderTraversal亦称（先序遍历））
——访问根结点的操作发生在遍历其左右子树之前。
② LNR：中序遍历(InorderTraversal)
——访问根结点的操作发生在遍历其左右子树之中（间）。
③ LRN：后序遍历(PostorderTraversal)
——访问根结点的操作发生在遍历其左右子树之后。
注意：
由于被访问的结点必是某子树的根，所以N(Node）、L(Left subtree）和R(Right subtree）又可解释为根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。
（二叉树遍历）

遍历的具体实现

LeetCode上有三道相关的题，分别求解二叉树的前序遍历、中序遍历和后序遍历

1、前序遍历

C++的迭代实现

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> preorderTraversal(TreeNode *root) {
        vector<int> path;  
        stack<TreeNode*> stk;//用栈保存一路遍历过来的根节点们，取完相应左子树的值后再pop出根节点去取右子树 
        while(root != NULL || !stk.empty())  
        {  
            if(root != NULL)  
            {  
                while(root)  
                {  
                    path.push_back(root->val);  
                    stk.push(root);  
                    root=root->left;  
                }  
            }  
            else{  
                root = stk.top()->right;  
                stk.pop();  
            }  
        }  
        return path; 
    }
};

2、中序遍历

Java的迭代实现

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<Integer>();
        Stack<TreeNode> stack = new  Stack<TreeNode>();
        while(root!=null || !stack.isEmpty()){
            while(root!=null){
                stack.push(root);
                root = root.left;
            }
            if(!stack.isEmpty()){
                TreeNode node = stack.pop();
                list.add(node.val);
                root = node.right;
            }
        }
        return list;
    }
}

3、后序遍历

Java的递归实现

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    private List<Integer> list = new ArrayList<Integer>();
    public List<Integer> postorderTraversal(TreeNode root) {
        if(root!=null){
            postorderTraversal(root.left);
            postorderTraversal(root.right);
            list.add(root.val);
        }
        return list;
    }
}

总结

处理此类问题，递归的思路会更加简单而直接，但是会带来更大的系统开销。迭代在思维上比较难，但执行很快。