一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 632|回复: 2
收起左侧

[Leetcode] Tree Traversal总结

[复制链接] |试试Instant~ |关注本帖
wandergogogo 发表于 2014-12-17 04:01:56 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
本帖最后由 wandergogogo 于 2014-12-17 04:14 编辑

Depth-first:pre-order, in-order, post-order

Pre-order:
preorder(node)
    if node == null then return
    visit(node)
    preorder(node.left)
    preorder(node.right)
  1. public List<Integer> preorder(TreeNode root){
  2.     List<Integer> res = new      LinkedList<Integer>();
  3.     if(root==null) return res;
  4.     res.add(root.val);
  5.     res.addAll(preorder(root.left));
  6.     res.addAll(preorder(root.right));
  7.     return res;
  8. }
复制代码
iterativePreorder(node)
    parentStack = empty stack
    while (node 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()
  1. public List<Integer>  iterativePreorder(TreeNode root){
  2.     List<Integer> res = new LinkedList<Integer>();
  3.     if(root==null) return res;
  4.     Stack<TreeNode> stack = new Stack<TreeNode>();
  5.     Stack.push(root);
  6.     while(!stack.isEmpty()){
  7.         TreeNode top = stack.pop();
  8.         res.add(top.val);
  9.         if(root.right!=null) stack.push(top.right);
  10.         if(root.left!=null) stack.push(top.left);
  11.     }
  12.     return res;
  13. }
复制代码
LeetCode Link: https://oj.leetcode.com/problems/binary-tree-preorder-traversal/

In-order:
inorder(node)
    if node == null then return
    inorder(node.left)
    visit(node)
    inorder(node.right)
  1. List<Integer> inorder(TreeNode root){
  2.     List<Integer> res = new LinkedList<Integer>();
  3.     if(root==null) return res;
  4.     res.addAll(inorder(root.left));
  5.     res.add(root.val);
  6.     res.addAll(inorder(root.right));
  7.     return res;
  8. }
复制代码
iterativeInorder(node)
    parentStack = empty stack
    while (not parentStack.isEmpty() or node != null)
        if (node != null)
            parentStack.push(node)
            node = node.left
        else
            noce = parentStack.pop()
            visit(node)
            node = node.right
  1. public List<Integer> iterativeInorder(TreeNode root){
  2.     List<Integer> res = new LinkedList<Integer>();
  3.     if(root==null) return res;
  4.     Stack<TreeNode> stack = new Stack<TreeNode>();
  5.     while(!stack.isEmpty() || root!=null){
  6.         if(root!=null){
  7.             stack.push(root);
  8.             root = root.left;
  9.         }else{
  10.             root = stack.pop();
  11.             res.add(root.val);
  12.             root = root.right;
  13.        }
  14.     }
  15.     return res;
  16. }
复制代码
LeetCode Link: https://oj.leetcode.com/problems/binary-tree-inorder-traversal/

Post-order:
postorder(node)
    if node == null then return
    postorder(node.left)
    postorder(node.right)
    visit(node)
  1. public List<Integer> postorder(TreeNode root){
  2.     List<Integer> res = new LinkedList<Integer>();
  3.     if(root==null) return res;
  4.     res.addAll(postorder(root.left));
  5.     res.addAll(postorder(root.right));
  6.     res.add(root.val);
  7.     return res;
  8. }
复制代码
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)
                node = peeknode.right
            else
                visit(peeknode)
                lastnodevisited = parentStack.pop()
  1. public List<Integer> iterativePostorder(TreeNode root){
  2.     List<Integer> res = new LinkedList<Integer>();
  3.     if(root==null) return res;
  4.     Stack<TreeNode> stack = new Stack<TreeNode>();
  5.     TreeNode lastNodeVisited = null;
  6.     while(!stack.isEmpty()||root!=null){
  7.         if(root!=null){
  8.             stack.push(root);
  9.             root = root.left;
  10.         }else{
  11.             TreeNode peekNode = stack.peek();
  12.             if(peeknode.right!=null && peeknode.right!=lastNodeVisited){
  13.                 root = peeknode.right;
  14.             }else{
  15.                 stack.pop();
  16.                 res.add(peeknode.val);
  17.                 lastNodeVisited = peeknode;
  18.            }
  19.         }
  20.     }
  21.     return res;
  22. }
复制代码
LeetCode Link: https://oj.leetcode.com/problems/binary-tree-postorder-traversal/



评分

2

查看全部评分

geng77 发表于 2014-12-17 06:12:57 | 显示全部楼层
good summary
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-4 06:02

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表