专栏首页深度学习技术前沿【LeetCode】一文详解二叉树的三大遍历:前序、中序和后序(python和C++实现)

【LeetCode】一文详解二叉树的三大遍历:前序、中序和后序(python和C++实现)

本文主要包括利用递归和栈的方法实现二叉树的前序、中序、后序遍历!

144. 二叉树的前序遍历

给定一个二叉树,返回它的 前序遍历。

示例:

输入: [1,null,2,3]

   1
     \
      2
     /
   3

输出: [1,2,3]

解题思路

1.1 树的前序遍历--非递归方法(栈)
  • 因为先访问根节点,所以直接将root的val放入答案(ans)容器
  • 利用stack来储存root。
  • 当左子树遍历完后,取出root接着遍历右子树。

C++实现:

/**
 * Definition for a binary tree node.
 * 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) {
        std::stack<TreeNode*> stack;
        vector<int> ans;
        while(root != NULL || !stack.empty()) {
            while(root != NULL) {
                stack.push(root);
                ans.push_back(root->val);
                root = root->left;
            }
            root = stack.top();
            stack.pop();
            root = root->right;
        }
        return ans;
    }
};

Python实现:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        if root is None:
            return []
        stack,res=[root,],[]
        while stack:
            root = stack.pop()
            if root is not None:
                res.append(root.val)
                if root.right is not None:
                    stack.append(root.right)
                if root.left is not None:
                    stack.append(root.left)
        return res
1.2 递归的思想

C++实现

class Solution {
public:
    vector<int> ans;
    vector<int> preorderTraversal(TreeNode* root) {
        if(root != NULL){
            ans.push_back(root -> val);
            preorderTraversal(root -> left);
            preorderTraversal(root -> right);
        }
        return ans;
    }
};

Python实现:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        res = []
        def preorder(root):
            if not root:return 
            res.append(root.val)
            preorder(root.left)
            preorder(root.right)
        preorder(root)
        return res

94. 二叉树的中序遍历

给定一个二叉树,返回它的中序遍历。

示例:

输入: [1,null,2,3]

   1
     \
      2
     /
   3

输出: [1,2,3]

解题思路

2.1 利用栈的思想

C++实现:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> stack;
        //s.push(root);
        while(root || s.size() > 0){
            while(root){
                stack.push(root);
                root = root->left;
            }
            root = stack.top(); 
            stack.pop();
            res.push_back(root->val);
            root = root->right;
        }
        return res;
    }
};

python实现:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        res = []
        stack = []
        while root or stack:
            # 把左子树压入栈中
            while root:
                stack.append(root)
                root = root.left
            # 输出 栈顶元素
            root = stack.pop()
            res.append(root.val)
            # 遍历右子树
            root = root.right
        return res
2.2 递归的思想

C++实现:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> ans;
    vector<int> inorderTraversal(TreeNode* root) {
        if(root != NULL){
            inorderTraversal(root -> left);
            ans.push_back(root -> val);
            inorderTraversal(root -> right);
        }
        return ans;
    }
};

Python实现:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        res = []
        def inorder(root):
            if not root:return 
            inorder(root.left)
            res.append(root.val)
            inorder(root.right)
        inorder(root)
        return res

145. 二叉树的后序遍历

给定一个二叉树,返回它的 后序 遍历。

示例:

输入: [1,null,2,3]

   1
     \
      2
     /
   3

输出: [1,2,3]

解题思路

3.1 利用迭代的思想(栈)

C++实现:

  • 先遍历左节点直到左节点为null。
  • 开始遍历右节点,若该右节点有左节点,优先遍历左节点。
  • 使用rightchild来记录右节点是否已被遍历过。若是:则说明以该点为根的子树已被遍历,输出根节点。若否:就开始遍历右节点,回到第二步。
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> ans;
        stack<TreeNode*> stk;
        TreeNode* cur = root;
        TreeNode* rightchild = NULL;
        while(cur || !stk.empty()){
            while(cur != NULL){
                stk.push(cur);
                cur = cur -> left;
            }
            cur = stk.top();
            if(!cur -> right|| rightchild == cur -> right){
                ans.push_back(cur -> val);
                stk.pop();
                rightchild = cur;
                cur = NULL;
            }
            else{
                rightchild = NULL;
                cur = cur -> right;
            }
        }
        return ans;
    }
};

Python实现:

  • 从根节点开始依次迭代,弹出栈顶元素输出到输出列表中,然后依次压入它的所有孩子节点,按照从上到下、从左至右的顺序依次压入栈中。
  • 因为深度优先搜索后序遍历的顺序是从下到上、从左至右,所以需要将输出列表逆序输出。
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        if root is None:
            return []

        stack, output = [root, ], []
        while stack:
            root = stack.pop()
            output.append(root.val)
            if root.left is not None:
                stack.append(root.left)
            if root.right is not None:
                stack.append(root.right)
                
        return output[::-1]

3.2 递归的思想

C++实现:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> ans;
    vector<int> postorderTraversal(TreeNode* root) {
        if(root != NULL){
            postorderTraversal(root->left);
            postorderTraversal(root->right);
            ans.push_back(root -> val);
        }
        return ans;
    }
};

Python实现:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        res = []
        def postorder(root):
            if not root:
                return 
            postorder(root.left)
            postorder(root.right)
            res.append(root.val)
        postorder(root)
        return res

本文分享自微信公众号 - 深度学习技术前沿(gh_a540734f538c),作者:murufeng

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-04-16

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Yann Lecun纽约大学《深度学习》2020课程笔记中文版,干货满满!

    【导读】Yann Lecun在纽约大学开设的2020春季《深度学习》课程,干货满满。在课程网站上出了最新的中文版课程笔记。

    深度学习技术前沿公众号博主
  • 8款值得学习的科研论文作图软件!

    科研绘图在国外已经非常流行,且被高度重视,国内科研人员也越来越重视科研方面的绘图。

    深度学习技术前沿公众号博主
  • CVPR 2020丨基于点云的3D物体检测新框架

    本文介绍的是CVPR2020入选论文《HVNet: Hybrid Voxel Network for LiDAR Based 3D Object Detecti...

    深度学习技术前沿公众号博主
  • leecode刷题(24)-- 翻转二叉树

    二叉树问题,我们首先要想到的使用递归的方式来解决,有了这个思路,处理这道问题就很简单了:先互换根节点的左右节点,然后递归地处理左子树,再递归地处理右子树,直到所...

    希希里之海
  • LeetCode 114. 二叉树展开为链表(递归)

    来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/flatten-binary-tree-to-link...

    Michael阿明
  • BST & AVL 二分搜索树 & 平衡二叉树的实现原理

    本文完整的实现了基本的BST,由于注重的是逻辑和原理的实现,所以没有采用泛型。注意方法的访问修饰符。

    大学里的混子
  • 【leetcode刷题】T129-翻转二叉树

    https://leetcode-cn.com/problems/invert-binary-tree/

    木又AI帮
  • leetcode226——翻转二叉树

    故事尾音
  • 226 Invert Binary Tree

    /** * Definition for a binary tree node. * function TreeNode(val) { * thi...

    用户1624346
  • LeetCode 783 & 530 Distance Between BST Nodes

    Given a Binary Search Tree (BST) with the root node root, return the minimum dif...

    大学里的混子

扫码关注云+社区

领取腾讯云代金券