资讯专栏INFORMATION COLUMN

Inorder Preorder Postorder

caikeal / 1762人阅读

摘要:题目链接参考这篇文章链接题目链接还是一样的,用,或者保存和。题目链接题目链接按照的顺序最后再一下。

Inorder Binary Tree Inorder Traversal

lc题目链接:https://leetcode.com/problems...

recursion:

public class Solution {
    public List inorderTraversal(TreeNode root) {
        List result = new ArrayList();
        dfs(root, result);
        return result;
    }
    
    private void dfs(TreeNode root, List result) {
        // base case
        if(root == null) return;
        dfs(root.left, result);
        result.add(root.val);
        dfs(root.right, result);
    }
}

iteration:

public class Solution {
    public List inorderTraversal(TreeNode root) {
        List result = new ArrayList();
        // stack
        Stack stack = new Stack();
        TreeNode node = root;
        while(!stack.isEmpty() || node != null) {
            while(node != null) {
                stack.push(node);
                node = node.left;
            }
            node = stack.pop();
            result.add(node.val);
            node = node.right;
        }
        return result;
    }
}

morris: 参考这篇文章
http://www.cnblogs.com/AnnieK...

public class Solution {
    public List inorderTraversal(TreeNode root) {
        /* morris: connect the node with its post if post != cur.next(cur.right == null)
         * add current when cur.left == null
         */
         List result = new ArrayList();
         TreeNode prev = null, cur = root;
         while(cur != null) {
             // reach the left most part, just add
             if(cur.left == null) {
                 result.add(cur.val);
                 // right connect to current"s post, null if finish traverse
                 cur = cur.right;
             }
             else {
                 prev = cur.left;
                 while(prev.right != null && prev.right != cur) prev = prev.right;
                 // connect prev with current: connect node with its post
                 if(prev.right == null) {
                     prev.right = cur;
                     cur = cur.left;
                 }
                 // recover the tree
                 else {
                     prev.right = null;
                     result.add(cur.val);
                     cur = cur.right;
                 }
             }
             
         }
         
         return result;
    }
}
Inorder Successor in BST

链接:https://leetcode.com/problems...

recursion:

public class Solution {
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        // base case
        if(root == null) return null;
        // left or root
        if(p.val < root.val) {
            TreeNode left = inorderSuccessor(root.left, p);
            return left == null ? root : left;
        }
        else return inorderSuccessor(root.right, p);
    }
}

iteration:

public class Solution {
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        TreeNode succ = null;
        while(root != null) {
            if(p.val < root.val) {
                succ = root;
                root = root.left;
            }
            else root = root.right;
        }
        
        return succ;
    }
}
173. Binary Search Tree Iterator

题目链接:https://leetcode.com/problems...
还是一样的,iteration用stack,或者morris保存prev和cur。

public class BSTIterator {
    Stack stack;
    public BSTIterator(TreeNode root) {
        stack = new Stack();
        // get the first node
        getAllLeft(root);
    }
    
    private void getAllLeft(TreeNode node) {
        while(node != null) {
            stack.push(node);
            node = node.left;
        }
    }
    
    /** @return whether we have a next smallest number */
    public boolean hasNext() {
        return !stack.isEmpty();
    }

    /** @return the next smallest number */
    public int next() {
        if(!hasNext()) return -1;
        
        TreeNode node = stack.pop();
        if(node.right != null) getAllLeft(node.right);
        return node.val;
    }
}
Preorder Binary Tree Preorder Traversal

题目链接:https://leetcode.com/problems...

recursion:

public class Solution {
    public List preorderTraversal(TreeNode root) {
        // recursion
        List result = new ArrayList();
        dfs(root, result);
        return result;
    }
    
    private void dfs(TreeNode root, List result) {
        // base case
        if(root == null) return;
        
        result.add(root.val);
        dfs(root.left, result);
        dfs(root.right, result);
    }
}

iteration:

public class Solution {
    public List preorderTraversal(TreeNode root) {
        // iteration: use stack
        List result = new ArrayList();
        if(root == null)  return result;
        
        Stack stack = new Stack();
        stack.push(root);
        while(!stack.isEmpty()) {
            TreeNode cur = stack.pop();
            result.add(cur.val);
            
            if(cur.right != null) stack.push(cur.right);
            if(cur.left != null) stack.push(cur.left);
        }
        
        return result;
    }
}

morris:

public class Solution {
    public List preorderTraversal(TreeNode root) {
        // morris: connect cur with its post in inorder
        // add as long as finding the post
        List result = new ArrayList();
        TreeNode cur = root, prev = null;
        while(cur != null) {
            // left is null, need to go to right
            if(cur.left == null) {
                result.add(cur.val);
                cur = cur.right;
            }
            else {
                prev = cur.left;
                // find the post in inorder
                while(prev.right != null && prev.right != cur) prev = prev.right;
                // connect with post and add
                if(prev.right == null) {
                    prev.right = cur;
                    result.add(cur.val);
                    cur = cur.left;
                }
                // recover the tree
                else {
                    prev.right = null;
                    cur = cur.right;
                }
            }
        }
        
        return result;
    }
}
Postorder Binary Tree Postorder Traversal

题目链接:https://leetcode.com/problems...

recursion:

public class Solution {
    public List postorderTraversal(TreeNode root) {
        List result = new ArrayList();
        dfs(root, result);
        return result;
    }
    
    private void dfs(TreeNode root, List result) {
        if(root == null)  return;
        
        dfs(root.left, result);
        dfs(root.right, result);
        result.add(root.val);
    }
}

iteration:

public class Solution {
    public List postorderTraversal(TreeNode root) {
        List result = new ArrayList();
        if(root == null)  return result;
        
        // right -> left -> reverse
        Stack stack = new Stack();
        stack.push(root);
        while(!stack.isEmpty()) {
            TreeNode cur = stack.pop();
            result.add(cur.val);
            if(cur.left != null) stack.push(cur.left);
            if(cur.right != null) stack.push(cur.right);
        }
        Collections.reverse(result);
        return result;
    }
}

morris: 按照root -> right -> left的顺序最后再reverse一下。

public class Solution {
    public List postorderTraversal(TreeNode root) {
        List result = new ArrayList();
        // root -> right -> left
        TreeNode cur = root, prev = null;
        while(cur != null) {
            // right == null, go to left
            if(cur.right == null) {
                result.add(cur.val);
                cur = cur.left;
            }
            else {
                prev = cur.right;
                while(prev.left != null && prev.left != cur) {
                    prev = prev.left;
                }
                // connect according to inorder but right first: right->root->left
                // leftmost.left = root
                if(prev.left == null) {
                    result.add(cur.val);
                    prev.left = cur;
                    cur = cur.right;
                }
                else {
                    prev.left = null;
                    cur = cur.left;
                }
            }
        }
        
        Collections.reverse(result);
        return result;
    }
}

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

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

相关文章

  • 刷题日记Day2 | 构造二叉树

    摘要:代码实现构建二叉树节点对应的值就是后序遍历数组的最后一个元素在中序遍历数组中的索引左子树的节点个数递归构造左右子树 把题目的要求细化,搞清楚根节点应该做什么,然...

    Hwg 评论0 收藏0
  • Construct Binary Tree from Traversal

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

    wenshi11019 评论0 收藏0
  • 推导二叉树的遍历结果

    摘要:推导前序序列已知二叉树的中序序列是,后序序列是,求前序序列。二叉树的中序序列是按照左子树,根,右子树的顺序排列的,根将左子树的序列和右子树的序列分割在左右两边。 推导前序序列 已知二叉树的中序序列是ABCDEFG,后序序列是BDCAFGE,求前序序列。 思路 showImg(https://segmentfault.com/img/bVW1es?w=723&h=431); 二叉树的后序...

    joy968 评论0 收藏0
  • 二叉树遍历算法收集(先序 preorder,后序 postorder,中序 inorder) 循环+

    摘要:指的是的位置。算法比较简单,算法比较难想,可是原题都说了 preorder: root-left-rightinorder: left-root-rightpostorder: left-right-root order指的是root的位置。 recursive算法比较简单,iterative算法比较难想,可是leetcode原题都说了: recursive method is tri...

    沈建明 评论0 收藏0
  • 我的面试准备过程--leetcode树

    摘要:由遍历结果反求树分析递归分治,第一层需要找到相应的遍历结果,对数组来说,问题转化为找下标问题对前序中序遍历结果来说前序左右中序左右因此,中序中的下标可求,为对每一层来说,左子树的长度为,右子树的长度为,左子树前序为至,中序为至,可以使  由遍历结果反求树 分析:递归分治,第一层需要找到相应的遍历结果,对数组来说,问题转化为找下标问题 对前序、中序遍历结果来说 前序:[root,[左...

    wenyiweb 评论0 收藏0

发表评论

0条评论

最新活动
阅读需要支付1元查看
<