[LintCode/LeetCode] Binary Tree InOrder Traversal

tomorrowwu 发布于2019-08-14 15:39 / 2763人阅读

摘要：递归法不说了，栈迭代的函数是利用的原理，从根节点到最底层的左子树，依次入堆栈。然后将出的结点值存入数组，并对出的结点的右子树用函数继续迭代。

Problem

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

Example

Given binary tree {1,#,2,3},

return [1,3,2].

Challenge

Can you do it without recursion?

Note

递归法不说了，栈迭代的helper函数是利用stack的LIFO原理，从根节点到最底层的左子树，依次push入堆栈。然后将pop出的结点值存入数组，并对pop出的结点的右子树用helper函数继续迭代。

Solution

Recursion

public class Solution {
    public ArrayList inorderTraversal(TreeNode root) {
        ArrayList res = new ArrayList();
        if (root == null) return res;
        helper(root, res);
        return res;
    }
    public void helper(TreeNode root, ArrayList res) {
        if (root.left != null) helper(root.left, res);
        res.add(root.val);
        if (root.right != null) helper(root.right, res);
    }
}

Stack Iteration

public class Solution {
    public ArrayList inorderTraversal(TreeNode root) {
        ArrayList res = new ArrayList();
        Stack stack = new Stack();
        if (root == null) return res;
        helper(stack, root);
        while (!stack.isEmpty()) {
            TreeNode cur = stack.pop();
            res.add(cur.val);
            if (cur.right != null) helper(stack, cur.right);
        }
        return res;
    }
    public void helper(Stack stack, TreeNode root) {
        stack.push(root);
        while (root.left != null) {
            root = root.left;
            stack.push(root);
        }
    }
}

Another Stack Iteration

public class Solution {
    public ArrayList inorderTraversal(TreeNode root) {
        ArrayList res = new ArrayList<>();
        Stack stack = new Stack<>();
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.add(cur);
                cur = cur.left;
            }
            cur = stack.pop();
            res.add(cur.val);
            cur = cur.right;
        }
        return res;
    }
}

GPU云服务器云服务器 binary-tree binary-search-tree Inorder Traversal

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

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

[LintCode/LeetCode] Construct Binary Tree from Tr

摘要：做了几道二分法的题目练手，发现这道题已经淡忘了，记录一下。这道题目的要点在于找的区间。边界条件需要注意若或数组为空，返回空当前进到超出末位，或超过，返回空每次创建完根节点之后，要将加，才能进行递归。 Construct Binary Tree from Inorder and Preorder Traversal Problem Given preorder and inorder t...

马忠志 2019-08-14 15:40 评论0 收藏0
[LintCode/LeetCode] Binary Tree Preorder Traversal

摘要：当你被的时候，人家问，一定要说，当然可以啦所以，不用，怎么办幸好，这是一道的题目，只要逐层遍历，就可以了。所以，试一试用堆栈的做法吧记得的特点是后入先出哦 Problem Given a binary tree, return the preorder traversal of its nodes values. Example Given: 1 / 2 3 ...

Vixb 2019-08-14 15:39 评论0 收藏0
[LintCode/LeetCode] Binary Tree Level Order Traver

Problem Given a binary tree, return the level order traversal of its nodes values. (ie, from left to right, level by level). For example:Given binary tree {3,9,20,#,#,15,7}, 3 / 9 20 / ...

makeFoxPlay 2019-08-14 15:48 评论0 收藏0
[LintCode/LeetCode] Binary Tree Zigzag Level Orde

Problem Given a binary tree, return the zigzag level order traversal of its nodes values. (ie, from left to right, then right to left for the next level and alternate between). Example Given binary tr...

AlphaGooo 2019-08-14 15:40 评论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