`

LeetCode - Binary Tree Traversal

 
阅读更多

Pre-order

preorder(node)
  if node == null then return
  visit(node)
  preorder(node.left) 
  preorder(node.right)
iterativePreorder(node)
  parentStack = empty stack
  while (not parentStack.isEmpty() or node ≠ null)
    if (node ≠ null) 
      visit(node)
      if(node.right ≠ null) parentStack.push(node.right) 
      node = node.left   
    else     
      node = parentStack.pop()

In-order

inorder(node)
  if node == null then return
  inorder(node.left)
  visit(node)
  inorder(node.right)
iterativeInorder(node)
  parentStack = empty stack
  while (not parentStack.isEmpty() or node ≠ null)
    if (node ≠ null)
      parentStack.push(node)
      node = node.left
    else
      node = parentStack.pop()
      visit(node)
      node = node.right

Post-order

postorder(node)
  if node == null then return
  postorder(node.left)
  postorder(node.right)
  visit(node)
iterativePostorder(node)
  parentStack = empty stack  
  lastnodevisited = null 
  while (not parentStack.isEmpty() or node ≠ null)
    if (node ≠ null)
      parentStack.push(node)
      node = node.left
    else
      peeknode = parentStack.peek()
      if (peeknode.right ≠ null and 
          lastnodevisited ≠ peeknode.right) 
        /* if right child exists AND traversing node 
         from left child, move right */
        node = peeknode.right
      else
        visit(peeknode)
        lastnodevisited = parentStack.pop() 

 

Pre-order:

public List<Integer> preorderTraversal(TreeNode node) {
    List<Integer> list = new LinkedList<Integer>();
    Stack<TreeNode> stack = new Stack<TreeNode>();
    while(!stack.isEmpty() || node != null) {
        if(node != null) {
            list.add(node.val);
            if(node.right != null) stack.push(node.right);
            node = node.left;
        } else {
            node = stack.pop();
        }
    }
    return list;
}

 

In-order:

private List<Integer> inorderIterative(TreeNode node) {
    List<Integer> list = new ArrayList<Integer>();
    Stack<TreeNode> stack = new Stack<TreeNode>();
    while(!stack.isEmpty() || node != null) {
        if(node != null) {
            stack.push(node);
            node = node.left;
        } else {
            TreeNode p = stack.pop();
            list.add(p.val);
            node = p.right;
        }
    }
    return list;
}

 

Posr-order:

private List<Integer> postorderIterative(TreeNode node) {
    List<Integer> list = new ArrayList<Integer>();
    Stack<TreeNode> stack = new Stack<TreeNode>();
    TreeNode last = null;
    while(!stack.empty() || node != null) {
        if(node != null) {
            stack.push(node);
            node = node.left;
        } else {
            TreeNode p = stack.peek();
            if(p.right != null && p.right != last) {
                node = p.right;
            } else {
                list.add(p.val);
                last = stack.pop();
            }
        }
    }
    return list;
}

 

Reference:

http://en.wikipedia.org/wiki/Tree_traversal#Implementations

分享到:
评论

相关推荐

    java-leetcode-107-binary-tree-level-order-traversal

    java java_leetcode-107-binary-tree-level-order-traversal

    java-leetcode-102-binary-tree-level-order-traversal

    java java_leetcode-102-binary-tree-level-order-traversal

    js-leetcode题解之107-binary-tree-level-order-traversal-ii.js

    通过LeetCode题解的这个文件“js-leetcode题解之107-binary-tree-level-order-traversal-ii.js”,我们可以学习如何使用JavaScript编写二叉树层序遍历的变种,以及如何处理和操作队列数据结构。

    js-leetcode题解之144-binary-tree-preorder-traversal.js

    对于LeetCode上编号为144的题目“Binary Tree Preorder Traversal”,我们可以采用递归或非递归的方式来解决。 首先,递归方法是前序遍历实现中最直观的一种。在递归函数中,我们首先将根节点的值添加到结果数组中...

    python-leetcode题解之107-Binary-Tree-Level-Order-Traversal-II

    2. 在LeetCode平台上,问题编号107的题目是“Binary Tree Level Order Traversal II”,它要求对给定的二叉树进行反向层级遍历,即从最后一层到第一层的顺序输出节点值。 3. 反向层级遍历算法可以通过先进行正常的...

    python-leetcode题解之102-Binary-Tree-Level-Order-Traversal

    由于LeetCode平台提供了一个公共的编程问题库供开发者练习和提升编程能力,因此我们选择了其中的题目编号102,即"Binary Tree Level Order Traversal"(二叉树的层序遍历)。为了解决这个问题,我们通常需要掌握队列...

    python-leetcode题解之144-Binary-Tree-Preorder-Traversal

    在编写Python代码解决LeetCode上144题时,我们可以通过递归或迭代的方式实现二叉树的前序遍历。 使用递归方法时,通常定义一个辅助函数,该函数接收当前节点作为参数。如果当前节点为空,则直接返回;否则,首先...

    python-leetcode题解之145-Binary-Tree-Postorder-Traversal

    LeetCode是一个著名的在线编程平台,它为用户提供了大量的编程题目,用于练习和提升算法与编程技能。这些题目涵盖了各种难度等级,适合不同水平的开发者练习。通过解决这些题目,开发者可以为技术面试做好准备,也...

    python-leetcode题解之103-Binary-Tree-Zigzag-Level-Order-Traversal

    今天我们将详细讨论Python实现LeetCode第103题——二叉树的锯齿形层序遍历(Binary Tree Zigzag Level Order Traversal)的解决方案。 二叉树的锯齿形层序遍历要求我们以不同于传统层序遍历的方式输出树节点值,即...

    c语言-leetcode题解之0094-binary-tree-inorder-traversal.zip

    在解决LeetCode上的0094号问题“Binary Tree Inorder Traversal”时,C语言是实现算法的常用语言之一。该题目要求设计一个算法来遍历二叉树,并按照中序遍历的方式返回遍历的结果。这不仅需要理解中序遍历的原理,还...

    js-leetcode题解之145-binary-tree-postorder-traversal.js

    在JavaScript中实现二叉树后序遍历,是众多算法练习者在LeetCode上常遇到的题目之一。题目的主要任务是遍历给定的二叉树,并按照后序遍历的规则输出节点的值。后序遍历,也就是先遍历左子树,再遍历右子树,最后访问...

    js-leetcode题解之102-binary-tree-level-order-traversal.js

    在讨论JavaScript解决LeetCode题解的实践中,我们关注的焦点是102题:二叉树的层序遍历。层序遍历是指按照树的层次从上到下,从左到右的顺序遍历树中的节点。它是一种广泛应用的二叉树遍历方法,尤其在树结构的算法...

    js-leetcode题解之103-binary-tree-zigzag-level-order-traversal.js

    在本篇文章中,我们将深入探讨JavaScript编程语言用于解决LeetCode上的103号题目,即“二叉树的锯齿形层序遍历”。该题要求使用JavaScript编写一个函数,实现对给定二叉树进行层序遍历,但要求按照“Z”形的顺序输出...

    js-leetcode题解之94-binary-tree-inorder-traversal.js

    在LeetCode上,问题编号94的题目“Binary Tree Inorder Traversal”就是要求对给定的二叉树进行中序遍历,并返回遍历的结果。给定的二叉树用JavaScript对象来表示,每个节点的值为一个数字,节点结构包含值、左子...

    python-leetcode题解之094-Binary-Tree-Inorder-Traversal

    leetcode是全球知名的在线编程平台,提供各种编程题目的解法,供程序员学习和练习。本文将详细解读如何使用Python解决leetcode上的“二叉树的中序遍历”问题,题目编号为094。该题目的核心是要求开发者编写代码,对...

    四平方和定理leetcode-leetcode-practice:个人LeetCode练习代码

    94.binary-tree-inorder-traversal (二叉树的中序遍历) 101.symmetric-tree (对称二叉树) 102.binary-tree-level-order-traversal (二叉树的层序遍历) 104.maximum-depth-of-binary-tree (二叉树的最大深度) 105....

    leetcode1-240题中文题解,md格式,java

    4. leetcode-145-Binary-Tree-Postorder-Traversal.md:第145题,二叉树的后序遍历,是关于树结构和递归的问题。 5. leetCode-5-Longest-Palindromic-Substring.md:第5题,最长回文子串,考察字符串处理和动态规划...

    leetcode-tree

    144-Binary Tree Preorder Traversal94-Binary Tree Inorder Traversal145-Binary Tree Postorder Traversal(后续的非递归时间不够可以先跳过,有点难)层次遍历,队列辅助,相当于广搜。102-Binary Tree Level ...

    LeetCode-Hot-100

    5. **递归与函数**:递归是解决许多算法问题的有效手段,如"Binary Tree Level Order Traversal"使用层次遍历(广度优先搜索)求解。而"Factorial Trailing Zeroes"则通过递归计算阶乘尾部零的个数。 6. **复杂度...

    gasstationleetcode-leetcode-in-niuke:在牛客网上的在线编程中的leetcode在线编程题解

    binary-tree-postorder-traversal 树 binary-tree-preorder-traversal 链表 linked-list-cycle-ii 链表 linked-list-cycle 链表 copy-list-with-random-pointer 复杂度 single-number 动态规划 candy 贪心 gas-...

Global site tag (gtag.js) - Google Analytics