递归二叉树的序列打印、非递归二叉树的序列打印

我会带着你远行 2022-06-09 06:06 157阅读 0赞

*   *   *  递归二叉树的序列打印
         *  非递归二叉树的序列打印

--------------------

### 递归二叉树的序列打印 ###

请用递归方式实现二叉树的先序、中序和后序的遍历打印。

给定一个二叉树的根结点root，请依次返回二叉树的先序，中序和后续遍历(二维数组的形式)。

**我的提交**

# -*- coding:utf-8 -*-
    
    # class TreeNode:
    # def __init__(self, x):
    # self.val = x
    # self.left = None
    # self.right = None
    class TreeToSequence:
        def convert(self, root):
            # write code here
            result = [[], [], []]
            if not root:
                return result
            self.pre(root, result[0])
            self.inOrder(root, result[1])
            self.afterOrder(root, result[2])
            return result
    
        def pre(self, root, result):
            if not root.left and not root.right:
                result.append(root.val)
                return 
            result.append(root.val)
            if root.left:
                self.pre(root.left, result)
            if root.right:
                self.pre(root.right, result)
            return
    
        def inOrder(self,root, result):
            if not root.left and not root.right:
                result.append(root.val)
                return
            if root.left:
                self.inOrder(root.left, result)
            result.append(root.val)
            if root.right:
                self.inOrder(root.right, result)
            return
    
        def afterOrder(self, root, result):
            if not root.left and not root.right:
                result.append(root.val)
                return
            if root.left:
                self.afterOrder(root.left, result)
            if root.right:
                self.afterOrder(root.right, result)
            result.append(root.val)
    
            return

**参考答案**

class TreeToSequence {
    public:
        void pre(TreeNode* rt,vector &ret){
            ret.push_back(rt->val);
            if(rt->left) pre(rt->left,ret);
            if(rt->right) pre(rt->right,ret);
        }
        void mid(TreeNode* rt,vector &ret){
            if(rt->left) mid(rt->left,ret);
            ret.push_back(rt->val);
            if(rt->right) mid(rt->right,ret);
        }
        void aft(TreeNode* rt,vector &ret){
            if(rt->left) aft(rt->left,ret);
            if(rt->right) aft(rt->right,ret);
            ret.push_back(rt->val);
        }
        vector > convert(TreeNode* root) {
            vector A,B,C;
            vector > ret;
            pre(root,A); mid(root,B); aft(root,C);
            ret.push_back(A); ret.push_back(B); ret.push_back(C);
            return ret;
        }
    };

--------------------

### 非递归二叉树的序列打印 ###

请用非递归方式实现二叉树的先序、中序和后序的遍历打印。

给定一个二叉树的根结点root，请依次返回二叉树的先序，中序和后续遍历(二维数组的形式)。

> 参考文档：【数据结构与算法】二叉树递归与非递归遍历（附完整源码）  
> [http://blog.csdn.net/ns\_code/article/details/12977901/][http_blog.csdn.net_ns_code_article_details_12977901]

**我的提交**

# -*- coding:utf-8 -*-
    
    # class TreeNode:
    # def __init__(self, x):
    # self.val = x
    # self.left = None
    # self.right = None
    class TreeToSequence:
        def convert(self, root):
            # write code here
            result = [[],[],[]]
            if not root:
                return result
            self.pre(root, result[0])
            self.mid(root, result[1])
            self.after(root, result[2])
            return result
    
    
        def pre(self, root, result):
            """非递归前序遍历 """
            if not root:
                return
            stack = []
            stack.append(root)
    
            while stack:
                node = stack.pop()
                result.append(node.val)
                if node.right:
                    stack.append(node.right)
                if node.left:
                    stack.append(node.left)
    
        def mid(self, root, result):
            """非递归中序遍历 """
            def pushLeftChild(root, stack):
                p = root
                while p:
                    stack.append(p)
                    p = p.left
    
            stack = []
    
            pushLeftChild(root, stack)
    
            while stack:
                node = stack.pop()
                result.append(node.val)
                pushLeftChild(node.right, stack)
    
            return
    
    
        def after(self, root, result):
            """非递归后序遍历 """
            if not root:
                return
            stack1 = []
            stack2 = []
            stack1.append(root)
            while stack1:
                node = stack1.pop()
                stack2.append(node)
                if node.left:
                    stack1.append(node.left)
                if node.right:
                    stack1.append(node.right)
    
            while stack2:
                result.append(stack2.pop().val)
            return

[http_blog.csdn.net_ns_code_article_details_12977901]: http://blog.csdn.net/ns_code/article/details/12977901/