binary tree

Find Next Higher Key in BST (Given Parent)

找后继节点, 但是这里给了父节点. 很简单的考虑一下几种情况: 引用一下http://www.algoqueue.com/的图比如3, 有右节点, 所以我们返回右节点的最左节点(后继).. 比如2, 没有右节点, 但是2是父节点3的左节点, 所以返回3. 假设没有7, 6没有右节点(没有7), 但是6是3(父节点)的右节点,所以我们只能往上找, 直到找到3是8的左节点, 返回8. package Learning;/** import java.util.*; public class NextHigherKeyinBST { static class TreeNode { // Node 有 parent TreeNode parent; TreeNode left; TreeNode right; int val; private TreeNode(){} public TreeNode(TreeNode p, int val) { this.parent = p; this.val = val; } […]

[LintCode] Convert Sorted Array to Binary Search Tree With Minimal Height

public TreeNode sortedArrayToBST(int[] A) { // write your code here return rec(A,0, A.length – 1); } public TreeNode rec(int[] A, int start, int end) { if(start > end) return null; int mid = start + (end – start) / 2; TreeNode root = new TreeNode(A[mid]); root.left = rec(A,start,mid-1); root.right = rec(A,mid+1, end); return root; }

Date August 16, 2015
Category LintCode
Comments No Comments

[LintCode] Subtree

public boolean isSubtree(TreeNode T1, TreeNode T2) { // write your code here if(T2 == null) return true; else if(T1 == null) return false; else return isSameTree(T1, T2) || isSubtree(T1.left, T2) || isSubtree(T1.right, T2); } public boolean isSameTree(TreeNode T1, TreeNode T2) { if(T1 == null && T2 == null) return true; if(T1 == null || T2 […]

Date August 14, 2015
Category LintCode
Comments No Comments

[LintCode] Maximum Depth of Binary Tree

public int maxDepth(TreeNode root) { // write your code here if(root == null) return 0; return Math.max(maxDepth(root.left), maxDepth(root.right))+1; }

Date August 12, 2015
Category LintCode
Comments No Comments

[LintCode] Invert Binary Tree

public void invertBinaryTree(TreeNode root) { // write your code here if(root == null) return; invertBinaryTree(root.left); invertBinaryTree(root.right); TreeNode left = root.left; root.left = root.right; root.right = left; }

Date August 11, 2015
Category LintCode
Comments No Comments

Find Next Higher Key in BST (Given Parent)

[LintCode] Convert Sorted Array to Binary Search Tree With Minimal Height

[LintCode] Subtree

[LintCode] Maximum Depth of Binary Tree

[LintCode] Invert Binary Tree

书脊

这青苔碧瓦堆, 俺曾睡风流觉, 将五十年兴亡看饱.

Categories