树的遍历算法（递归，迭代）（C++，java）_c++目录树的迭代

树的遍历算法（递归，迭代）（C++，java）

最近刷力扣，记录一下树的各种遍历算法，分别用C++和java实现，基于递归和迭代。

基于递归的二叉树遍历

	所有树的遍历用递归来解决思路都是是十分清晰的，前序中序后序差距都差不多，就是改变一下位置。下面给出前序的代码。
1

• 前序 （当前节点+左子树+右子树）

//递归(java)
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if (root!=null){
            list.add(root.val);
            list.addAll(preorderTraversal(root.left));
            list.addAll(preorderTraversal(root.right));
        }
        return list;     
    }
1
2
3
4
5
6
7
8
9
10

//递归（C++）
public:
    vector<int> result;
    vector<int> preorderTraversal(TreeNode* root) {
        
         if(root){
            this.result.push_back(root->val);
            preorderTraversal(root->left);
            preorderTraversal(root->right);
        }
        return result;
    }
1
2
3
4
5
6
7
8
9
10
11
12

• 中序 （左子树+当前节点+右子树）

• 后序 （左子树+右子树+当前节点）

基于迭代的二叉树遍历

	基于迭代的二叉树遍历实现起来要稍微复杂一点，需要利用栈来实现，为了防止指针丢失，将迭代到的每一个节点都存入栈中。可以用以下模板。
	while(){
		while()
	}
1
2
3
4

• 前序

//java
public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        while(root!=null||!stack.isEmpty()){
            while(root!=null){
                list.add(root.val);
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            root = root.right;
        }
        return list;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

//c++
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result;
        vector<TreeNode*> stack;
        while(root||!stack.empty()){
            while(root){
                result.push_back(root->val);
                stack.push_back(root);
                root = root->left;
            }
            root=stack.back();
            stack.pop_back();
            root=root->right;
        }
        return result;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

• 中序
  中序方法和前序差不多，也是改变以下位置的事，下面就给出java的代码段。

while(root!=null||!stack.isEmpty()){
            while(root!=null){
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            list.add(root.val);
            root = root.right;
        }
1
2
3
4
5
6
7
8
9

• 后序
  后序迭代就要麻烦一些了，因为要遍历完所有孩子节点后才能存父节点，因此需要判断孩子节点是否全部遍历完成。所以借用一个临时树节点存储右孩子节点，当父节点上一个访问的为该右孩子节点，则表示孩子节点访问完成。

//java
public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode p = null;//临时节点
        while(root!=null||!stack.isEmpty()){
            while(root!=null){
                stack.push(root);
                root = root.left;
            }
            root = stack.peek();
            root = root.right;
            if(root==null||root==p){
                p = stack.pop();
                list.add(p.val);
                root = null;//防止重复访问
            }
        }
        return list;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

//c++
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*> st;
        TreeNode* p;//临时节点
        while(!st.empty()||root){
            while(root){
                st.push(root);
                root = root->left;
            }
            root = st.top();
            root = root->right;
            if(!root||root==p){
                root = st.top();
                st.pop();
                p=root;
                result.push_back(root->val);
                root = nullptr;//防止重复访问
            }
        }
        return result;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

N叉树的递归遍历（急着去吃饭，直接贴代码）

//c++(前序)
public:
    vector<int> res;
    vector<int> preorder(Node* root) {
        if(root){
            res.push_back(root->val);
            for(Node* each:root->children)
               preorder(each); 
        }
        return res;  
    }
1
2
3
4
5
6
7
8
9
10
11

后续遍历差不多，就是改变位置，代码就不给了。

N叉树的迭代遍历

• 前序

//java
public List<Integer> preorder(Node root) {
        Stack<Node> stack = new Stack<>();
        List<Integer> res = new ArrayList<>();
        if(root==null)
            return res;
        stack.push(root);
        while(!stack.isEmpty()){
            root = stack.pop();
            res.add(root.val);
            for(int i=root.children.size()-1;i>=0;i--){
                stack.push(root.children.get(i));
            }
        }
        return res;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

//c++
public:
    vector<int> preorder(Node* root) {
        stack<Node*> sk;
        vector<int> res;
        if(!root)
            return res;
        sk.push(root);
        while(!sk.empty()){
            root = sk.top();
            res.push_back(root->val);
            sk.pop();
            for(int i=root->children.size()-1;i>=0;i--){
                sk.push((root->children)[i]);
            }
        }
        return res; 
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

• 后序
  其实后序遍历挺有意思的，给个大致思路：“利用先序遍历的逆向思维，利用两个栈来实现反向压栈，正向出栈”。
  代码如下：

//java
public List<Integer> postorder(Node root) {
        Stack<Node> stk1 = new Stack<>();
        Stack<Node> stk2 = new Stack<>();
        List<Integer> res = new ArrayList<>();
        if(root==null)
            return res;
        stk2.push(root);
        while(!stk2.isEmpty()){
            stk1.push(stk2.peek());
            root = stk2.pop();
            for(Node each:root.children){
                stk2.push(each);
            }
        }
        while(!stk1.isEmpty()){
            res.add(stk1.pop().val);
        }
        return res;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

//c++
vector<int> postorder(Node* root) {
        vector<int> res;
        stack<Node*> st1;
        stack<Node*> st2;
        if(root==nullptr)
            return res;
        st1.push(root);
        while(!st1.empty()){
            root = st1.top();
            st2.push(root);
            st1.pop();
            for(Node* each:root->children){
                st1.push(each);
            }
        }
        while(!st2.empty()){
            res.push_back(st2.top()->val);
            st2.pop();
        }
        return res;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22