[LeetCode-Tree]Binary Tree Inorder & Preorder

taowen 发布于2019-08-16 10:26 / 1463人阅读

摘要：代码解题思路先序遍历，同样用迭代实现，借助栈。先将根节点入栈先序遍历，所以直接出根节点因为顺序是根，左节点，右节点，所以我们在压栈的时候要先压右节点，再压左节点。所以我们自定义了一个类，添加了的属性，来表明该节点是否已经被访问过了。

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 [1,3,2].

1.解题思路

这里我们选用迭代来解题，借用压栈出栈来实现。
1）中序遍历，左节点，根，右节点，所以每次遇到root节点，我们就将其压入栈中，然后在判断它有没有左节点，有的话也压入栈中，直到树的最左边的叶子节点，第一步就结束了；
2）现在我们开始出栈，每次出栈的节点肯定不会再有左孩子了，但我们需要判断它是否有右孩子，如果有，我们要针对右节点再做step1的操作。

2.代码

public class Solution {
    Stack s=new Stack();
    public List inorderTraversal(TreeNode root) {
        List res =new ArrayList();
        if(root==null) return res;
        pushLeft(root);
        while(!s.empty()){
            TreeNode pnode=s.pop();
            res.add(pnode.val);
            if(pnode.right!=null){
                pushLeft(pnode.right);
            }
        }
        return res;
    }
    private void pushLeft(TreeNode root){
        TreeNode node=root.left;
        s.push(root);
        while(node!=null){
            s.push(node);
            node=node.left;
        }
    }
}

Binary Tree Preorder Traversal
Given a binary tree, return the preorder traversal of its nodes" values.

For example:
Given binary tree {1,#,2,3},
   1
    
     2
    /
   3
return [1,2,3].

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

1.解题思路

先序遍历，同样用迭代实现，借助栈。
1）先将根节点入栈
2）先序遍历，所以直接Pop出根节点
3）因为顺序是根，左节点，右节点，所以我们在压栈的时候要先压右节点，再压左节点。

public class Solution {
    public List preorderTraversal(TreeNode root) {
        List res=new ArrayList();
        if(root==null) return res;
        Stack s=new Stack();
        s.push(root);
        while(!s.empty()){
            TreeNode node=s.pop();
            res.add(node.val);
            if(node.right!=null)
                s.push(node.right);
            if(node.left!=null)
                s.push(node.left);
        }
        return res;
    }
}

Binary Tree Postorder Traversal
Given a binary tree, return the postorder traversal of its nodes" values.

For example:

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

return [3,2,1].

1.解题思路
后序遍历，本题比前两题稍微复杂一点，因为后序遍历，必然根节点会被访问到两次，一次是入栈，并访问其左节点，但还要考虑其是否有右节点，如果有右节点必须先输出右节点，所以我们不能马上将根节点立即出栈。
所以我们自定义了一个类，添加了isVisited的属性，来表明该节点是否已经被访问过了。

2.代码

public class Solution {
    Stack s=new Stack();
    public List postorderTraversal(TreeNode root) {
        List res=new ArrayList();
        if(root==null) return res;
        
        pushLeft(new DefinedTreeNode(root,false));
        while(!s.empty()){
            DefinedTreeNode dt=s.peek();
            if(dt.node.right==null||dt.isVisited){
                s.pop();
                res.add(dt.node.val);
            }
            else{
                dt.isVisited=true;
                pushLeft(new DefinedTreeNode(dt.node.right,false));
            }
            
            
        }
        return res;
    }
    private void pushLeft(DefinedTreeNode root){
        s.push(root);
        DefinedTreeNode dt=new DefinedTreeNode(root.node.left,false);
        while(dt.node!=null){
            s.push(dt);
            dt=new DefinedTreeNode(dt.node.left,false);
        }
    }
    class DefinedTreeNode {
        TreeNode node;
        boolean isVisited;
        DefinedTreeNode(TreeNode node, boolean isVisited){
            this.node=node;
            this.isVisited=isVisited;
        }
    }
}

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

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

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

Construct Binary Tree from Preorder and Inorder Tr

摘要：解题思路利用递归思想，先序遍历的第一个元素就是根节点，然后在中序遍历中寻找该节点，该节点左边的就是左子树，右边的是右子树。 Construct Binary Tree from Preorder and Inorder TraversalGiven preorder and inorder traversal of a tree, construct the binary tree. ...

tuomao 2019-08-16 10:26 评论0 收藏0
[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
Construct Binary Tree from Traversal

摘要：思路在的顺序里，先，然后再左右。所以根据可以知道的。接着再分别在和的里面重复找以及左右的过程。首先的包括和，以及对应的起始和结束位置，对应的起始和结束位置。返回值为，因为每个里要一个，同时找到它的和，左右节点通过返回值获得。同时的不需要了。 From Preorder and Inorder 思路在preorder的顺序里，先root，然后再左右。所以根据preorder可以知道roo...

wenshi11019 2019-08-14 17:11 评论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
Inorder Preorder Postorder

摘要：题目链接参考这篇文章链接题目链接还是一样的，用，或者保存和。题目链接题目链接按照的顺序最后再一下。 Inorder Binary Tree Inorder Traversal lc题目链接：https://leetcode.com/problems... recursion： public class Solution { public List inorderTraversa...

caikeal 2019-08-14 17:23 评论0 收藏0