leetcode 94. Binary Tree Inorder Traversal

wpw 发布于2019-08-15 10:54 / 937人阅读

摘要：题目要求中序遍历树，并将遍历结果添加到数组中。分别用递归和循环的方式结局。如果当前节点存在左子节点，则继续遍历左子树直到最后一个左子节点。如果栈顶元素有右子节点，则将其右子节点压入栈中作为，再继续遍历的左子节点。当和都为空时，遍历结束。

题目要求

Given a binary tree, return the inorder traversal of its nodes" values.

For example:
Given binary tree [1,null,2,3],
   1
    
     2
    /
   3
return [1,3,2].

Note: Recursive solution is trivial, could you do it iteratively?

中序遍历树，并将遍历结果添加到数组中。分别用递归和循环的方式结局。

递归

核心的思路就是先递归左侧子节点，之后读取中间节点的值，再递归右侧子节点。

    public List inorderTraversal(TreeNode root) {
        List result = new ArrayList();
        inorderTraversal(root, result);
        return result;
    }
    
    public void inorderTraversal(TreeNode root, List result){
        if(root==null) return;
        inorderTraversal(root.left, result);
        result.add(root.val);
        inorderTraversal(root.right, result);
    }

循环

这里需要利用栈的数据结构。如果当前节点存在左子节点，则继续遍历左子树直到最后一个左子节点。然后依次处理栈中的元素。如果栈顶元素有右子节点，则将其右子节点压入栈中作为root，再继续遍历root的左子节点。当root和stack都为空时，遍历结束。

    public List inorderTraversal2(TreeNode root) {
        List result = new ArrayList();
        if(root==null) return result;
        
        LinkedList stack = new LinkedList();
        do{
            while(root!=null){
                stack.push(root);
                root = root.left; 
            }
            root = stack.pop();
            result.add(root.val);
            root = root.right;
        }while(!(stack.isEmpty() && root==null));
        return result;
    }

想要了解更多开发技术，面试教程以及互联网公司内推，欢迎关注我的微信公众号！将会不定期的发放福利哦~

idc机房托管混合云 binary-tree binary-search-tree Inorder Traversal

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/67420.html

leetcode讲解--94. Binary Tree Inorder Traversal

摘要：题目地址嗯，经典的题目，中序遍历二叉树。代码如下中序遍历先序遍历后序遍历是不是简单的不要不要的，递归就是这么美。右孩子后压栈全部释放出来嗯，总的来说用迭代遍历确实烧脑，没什么性能上的特殊需求还是用递归写法吧，对程序员友好哦。 94. Binary Tree Inorder Traversal Given a binary tree, return the inorder travers...

henry14 2019-07-25 11:22 评论0 收藏0
LeetCode 之 JavaScript 解答第94题 —— 二叉树的中序遍历

摘要：小鹿题目二叉树中序遍历给定一个二叉树，返回它的中序遍历。通常递归的方法解决二叉树的遍历最方便不过，但是我还是喜欢增加点难度，用一般的迭代循环来实现。 Time：2019/4/25Title:Binary Tree Inorder TraversalDifficulty: MediumAuthor:小鹿题目：Binary Tree Inorder Traversal（二叉树中序遍历...

Jason 2019-08-23 17:19 评论0 收藏0
94. Binary Tree Inorder Traversal

摘要：题目解答合并两个直接就好啦的方法很巧妙，当时想了很久也没做出来，所以这里标注一下题目：Given a binary tree, return the inorder traversal of its nodes values. For example:Given binary tree [1,null,2,3], 1 2 / 3 return ...

dackel 2019-08-14 14:12 评论0 收藏0
[Leetcode] Construct Binary Tree from Traversal 根据

摘要：二分法复杂度时间空间思路我们先考察先序遍历序列和中序遍历序列的特点。对于中序遍历序列，根在中间部分，从根的地方分割，前半部分是根的左子树，后半部分是根的右子树。 Construct Binary Tree from Preorder and Inorder Traversal Given preorder and inorder traversal of a tree, constru...

caoym 2019-08-14 12:32 评论0 收藏0
[LintCode/LeetCode] Binary Tree InOrder Traversal

摘要：递归法不说了，栈迭代的函数是利用的原理，从根节点到最底层的左子树，依次入堆栈。然后将出的结点值存入数组，并对出的结点的右子树用函数继续迭代。 Problem Given a binary tree, return the inorder traversal of its nodes values. Example Given binary tree {1,#,2,3}, 1 ...

tomorrowwu 2019-08-14 15:39 评论0 收藏0