精华内容
下载资源
问答
  • 二叉树的后序遍历

    2020-11-09 22:38:37
    二叉树的后序遍历二叉树的后序遍历中,根结点的访问是在其两颗子树都遍历完后进行的。后序遍历如下定义。 1.按后序遍历左子树 2.按后序遍历右子树 3.访问根结点 void postOrder(BinaryTreeNode root){ if(root !...

    二叉树的后序遍历

    在二叉树的后序遍历中,根结点的访问是在其两颗子树都遍历完后进行的。后序遍历如下定义。
    1.按后序遍历左子树
    2.按后序遍历右子树
    3.访问根结点

    void postOrder(BinaryTreeNode root){
      if(root != null){
        PostOrder(root.getLeft());
        PostOrder(root.getRight());
        System.out.println(root.getData());
      }
    }
    
    时间复杂度o(n) 空间复杂度o(n)
    
    展开全文
  • Java实现 LeetCode 145 二叉树的后序遍历

    万次阅读 多人点赞 2020-02-22 15:10:55
    145. 二叉树的后序遍历 给定一个二叉树,返回它的 后序 遍历。 示例: 输入: [1,null,2,3] 1 \ 2 / 3 输出: [3,2,1] 进阶: 递归算法很简单,你可以通过迭代算法完成吗? /** * Definition for a binary tree ...

    145. 二叉树的后序遍历

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

    示例:

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

       1
        \
         2
        /
       3 
    

    输出: [3,2,1]
    进阶: 递归算法很简单,你可以通过迭代算法完成吗?

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
      public List<Integer> postorderTraversal(TreeNode root) {//非递归写法
        List<Integer> res = new ArrayList<Integer>();
        if(root == null)
            return res;
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode pre = null;
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode curr = stack.peek();            
            if((curr.left == null && curr.right == null) ||
               (pre != null && (pre == curr.left || pre == curr.right))){ 
                            //如果当前结点左右子节点为空或上一个访问的结点为当前结点的子节点时,当前结点出栈
                res.add(curr.val);
                pre = curr;
                stack.pop();
            }else{
                if(curr.right != null) stack.push(curr.right); //先将右结点压栈
                if(curr.left != null) stack.push(curr.left);   //再将左结点入栈
            }            
        }
        return res;        
    }
    }
    
    展开全文
  • 二叉树利用前序遍历和中序遍历求二叉树及二叉树的后序遍历 二叉树的三种遍历分别是前序遍历,中序遍历以及后序遍历,遍历的核心在于根的位置,可以简记为: 前序遍历->根,左,右 中序遍历->左,根,右 后序...

    二叉树利用前序遍历和中序遍历求二叉树及二叉树的后序遍历

    二叉树的三种遍历分别是前序遍历,中序遍历以及后序遍历,遍历的核心在于根的位置,可以简记为:
    前序遍历->根,左,右
    中序遍历->左,根,右
    后序遍历->左,右,根
    如何运用其中两个求二叉树呢?是不是都可以呢?答案时否定的。
    前序遍历和后序遍历确定的是根的位置,而中序遍历是二叉树的左右子树,所以如果同时有二叉树的前序遍历和后序遍历是不能求出二叉树的。下面给出已知前序遍历和中序遍历求二叉树及二叉树的方法
    前序遍历:a b d e g c f h
    中序遍历:d b e g a c h f
    分析:由前序遍历可知a为根节点,由中序遍历知d b e g为a的左子树,c h f为右子树,对左子树分析,b为根节点,d为左子树,e g为右子树,前序中序均为e g则e为g的父节点,g是右子树;再分析a的右子树,c为右子树的根,h f和f h的顺序可知h为c的右子树,f为h的左子树
    结果在这里插入图片描述
    后序遍历根据后序遍历的规则来的!!!

    展开全文
  • Leetcode 二叉树的后序遍历

    热门讨论 2020-10-23 23:48:00
    Leetcode原题链接:二叉树的后序遍历 二叉树的后序遍历:按照访问左子树——右子树——根节点的方式遍历这棵树,而在访问左子树或者右子树的时候,我们按照同样的方式遍历,直到遍历完整棵树。因此整个遍历过程天然...

    0 题目描述

    Leetcode原题链接:二叉树的后序遍历
    在这里插入图片描述

    二叉树的后序遍历:按照访问左子树——右子树——根节点的方式遍历这棵树,而在访问左子树或者右子树的时候,我们按照同样的方式遍历,直到遍历完整棵树。因此整个遍历过程天然具有递归的性质,我们可以直接用递归函数来模拟这一过程。

    1 递归解法

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

    算法复杂度
    时间复杂度:O(n)O(n),其中 nn 为二叉树节点的个数。二叉树的遍历中每个节点会被访问一次且只会被访问一次。
    空间复杂度:O(n)O(n)。空间复杂度取决于递归的栈深度,而栈深度在二叉树为一条链的情况下会达到 O(n)O(n)的级别。

    2 迭代解法(堆栈)

    我们也可以用迭代的方式实现方法一的递归函数,两种方式是等价的,区别在于递归的时候隐式地维护了一个栈,而我们在迭代的时候需要显式地将这个栈模拟出来,其余的实现与细节都相同,具体可以参考下面的代码。

    class Solution:
        def postorderTraversal(self, root: TreeNode) -> List[int]:
            White, Gray = 0, 1
            res = []
            stack = [(White, root)]
            while stack:
                color, node = stack.pop()
                if not node: continue
                if color == White:
                    stack.append((Gray, node))
                    stack.append((White, node.right))
                    stack.append((White, node.left))
                else:
                    res.append(node.val)
            return res

    算法复杂度
    时间复杂度:访问每个节点恰好一次,时间复杂度为O(N)O(N),其中NN是节点的个数,也就是树的大小。
    空间复杂度:取决于树的结构,最坏情况存储整棵树,因此空间复杂度是O(N)O(N)

    3 Morris 后序遍历

    有一种巧妙的方法可以在线性时间内,只占用常数空间来实现后序遍历。这种方法即Morris遍历。

    # Definition for a binary tree node.
    # class TreeNode:
    #     def __init__(self, val=0, left=None, right=None):
    #         self.val = val
    #         self.left = left
    #         self.right = right
    class Solution(object):
        def postorderTraversal(self, root):
            """
            :type root: TreeNode
            :rtype: List[int]
            """
            def addPath(node: TreeNode):
                count = 0
                while node:
                    count += 1
                    res.append(node.val)
                    node = node.right
                i, j = len(res) - count, len(res) - 1
                while i < j:
                    res[i], res[j] = res[j], res[i]
                    i += 1
                    j -= 1
    
            if not root: return []
            node, res = root, []
            while node:
                pre = node.left
                if pre:
                    while pre.right and pre.right is not node:
                        pre = pre.right
                    if not pre.right:
                        pre.right = node
                        node = node.left
                        continue
                    else:
                        pre.right = None
                        addPath(node.left)
                node = node.right
    
            addPath(root)
            return res

    算法复杂度
    时间复杂度:O(n)O(n),其中nn是二叉树的节点数。没有左子树的节点只被访问一次,有左子树的节点被访问两次。
    空间复杂度:O(1)O(1)。只操作已经存在的指针(树的空闲指针),因此只需要常数的额外空间。

    参考资料

    二叉树的前序遍历
    二叉树的中序遍历 – Python实现三种解法

    展开全文
  • 145. 二叉树的后序遍历题目解题思路代码 题目 给定一个二叉树,返回它的 后序 遍历。 解题思路 简单,后序遍历 代码 class Solution { List<Integer> list=new ArrayList<>(); public List<...
  • 145. 二叉树的后序遍历 给定一个二叉树,返回它的 后序 遍历。 题目链接 题解: class Solution { public List<Integer> postorderTraversal(TreeNode root) { List<Integer> ret = new LinkedList&...
  • LeetCode 145 二叉树的后序遍历 题目链接 给定一个二叉树,返回它的 后序 遍历。 示例: 输入: [1,null,2,3] 1 \ 2 / 3 输出: [3,2,1] 看题目的意思是想让我们写个非递归的后序遍历,但那个非常复杂,所以我...
  • 根据二叉树的后序遍历以及中序遍历还原二叉树 【题目】假设一棵二叉树的后序遍历序列为 DGJHEBIFCA ,中序遍历序列为 DBGEHJACIF ,则其前序遍历序列为 ( ) 。A. ABCDEFGHIJB. ABDEGHJCFIC. ABDEGHJFICD. ...
  • 145. 二叉树的后序遍历 题解: 1. 题解一:递归后序遍历 第一种解决方法是使用递归。这是经典的方法,直截了当。我们可以定义一个辅助函数来实现递归。 2. 题解二:迭代后序遍历 代码: 1. 代码一:递归后序遍历 ...
  • C/C++描述 LeetCode 145. 二叉树的后序遍历

    千次阅读 多人点赞 2020-09-29 11:22:34
    二叉树的后序遍历   大家好,我叫亓官劼(qí guān jié ),在CSDN中记录学习的点滴历程,时光荏苒,未来可期,加油~博主目前仅在CSDN中写博客,唯一博客更新的地址为:亓官劼的博客 本文原创为亓官劼,请...
  • 94. 二叉树的中序遍历 题目描述 给定一个二叉树,返回它的中序 遍历。 示例: 输入: [1,null,2,3] 1 \ 2 / ...给定一个二叉树,返回它的 前序 ...二叉树的后序遍历 题目描述 给定一个二叉树,返回它的 后序 遍历。 示例...
  • 二叉树的后序遍历,非递归实现 思路: 后序遍历:左右根 1 开始找以cur根的所有的左侧节点入栈,此时cur在3的左侧空的位置,因为3的右侧没有节点,因此最后遍历节点3: 2 同理2,1节点。然后4,5节点一次入栈,此时...
  • 其实这道题和我们经常说的求二叉树的后序遍历序列不一样,大家一定要看清题意再做。二叉搜索树的特点是左子树比根结点小,右子树比根结点大。后序遍历最后一个元素是根结点,根结点左边的元素都比根结点小,根结点...
  • tree traversal (树的遍历) - 后序遍历 (postorder traversal) - 二叉树的后序遍历 1. tree traversal (树的遍历) 1.1 深度优先搜索 (depth-first search,DFS) 我们采用深度作为优先级,从根节点开始一直到达某个...
  • * @description : 二叉树的后序遍历序列 * @create : 2020/11/27 19:10 */ public class VerifySquenceOfBST { //输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回true,否则返回...
  • 二叉树的后序遍历非递归算法 关于 (1)如何利用前序遍历创建二叉树 (2)二叉树的前序、中序、后序递归遍历 (3)二叉树的前序、中序非递归遍历 都已经在之前两篇文章中说过了 利用前序遍历创建二叉树,二叉树的...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 22,752
精华内容 9,100
关键字:

二叉树的后序遍历