摘要:题目链接参考这篇文章链接题目链接还是一样的,用,或者保存和。题目链接题目链接按照的顺序最后再一下。
Inorder Binary Tree Inorder Traversal
lc题目链接:https://leetcode.com/problems...
recursion:
public class Solution { public ListinorderTraversal(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 ListinorderTraversal(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 ListInorder Successor in BSTinorderTraversal(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; } }
链接: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 { StackPreorder Binary Tree Preorder Traversalstack; 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; } }
题目链接:https://leetcode.com/problems...
recursion:
public class Solution { public ListpreorderTraversal(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 ListpreorderTraversal(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 ListPostorder Binary Tree Postorder TraversalpreorderTraversal(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; } }
题目链接:https://leetcode.com/problems...
recursion:
public class Solution { public ListpostorderTraversal(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 ListpostorderTraversal(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 ListpostorderTraversal(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
摘要:代码实现构建二叉树节点对应的值就是后序遍历数组的最后一个元素在中序遍历数组中的索引左子树的节点个数递归构造左右子树 把题目的要求细化,搞清楚根节点应该做什么,然...
摘要:思路在的顺序里,先,然后再左右。所以根据可以知道的。接着再分别在和的里面重复找以及左右的过程。首先的包括和,以及对应的起始和结束位置,对应的起始和结束位置。返回值为,因为每个里要一个,同时找到它的和,左右节点通过返回值获得。同时的不需要了。 From Preorder and Inorder 思路在preorder的顺序里,先root,然后再左右。所以根据preorder可以知道roo...
摘要:推导前序序列已知二叉树的中序序列是,后序序列是,求前序序列。二叉树的中序序列是按照左子树,根,右子树的顺序排列的,根将左子树的序列和右子树的序列分割在左右两边。 推导前序序列 已知二叉树的中序序列是ABCDEFG,后序序列是BDCAFGE,求前序序列。 思路 showImg(https://segmentfault.com/img/bVW1es?w=723&h=431); 二叉树的后序...
摘要:指的是的位置。算法比较简单,算法比较难想,可是原题都说了 preorder: root-left-rightinorder: left-root-rightpostorder: left-right-root order指的是root的位置。 recursive算法比较简单,iterative算法比较难想,可是leetcode原题都说了: recursive method is tri...
摘要:由遍历结果反求树分析递归分治,第一层需要找到相应的遍历结果,对数组来说,问题转化为找下标问题对前序中序遍历结果来说前序左右中序左右因此,中序中的下标可求,为对每一层来说,左子树的长度为,右子树的长度为,左子树前序为至,中序为至,可以使 由遍历结果反求树 分析:递归分治,第一层需要找到相应的遍历结果,对数组来说,问题转化为找下标问题 对前序、中序遍历结果来说 前序:[root,[左...
阅读 538·2021-11-18 10:02
阅读 1017·2021-11-02 14:41
阅读 586·2021-09-03 10:29
阅读 1862·2021-08-23 09:42
阅读 2683·2021-08-12 13:31
阅读 1147·2019-08-30 15:54
阅读 1910·2019-08-30 13:09
阅读 1402·2019-08-30 10:55