Binary Tree和Binary Search Tree
Binary Tree Binary Tree Example: 10 ==root /? ? ? 13? ? ? ? ? 15? cur /? ?? ? /? 21 72? ? ? 12? ? 2 ?/? null? ?null class TreeNode{ int value; TreeNode * left; TreeNode * right; TreeNode * parent //point to this node‘s parent node. } 基本知识点1: tree traverse 1. pre-order. 2.in-order. 3.post-order. 关键点:base case通常就是叶子节点下面的空节点。 ? Balanced binary tree: 对于树的任意一个节点,左子树和右子树的高度差不超过1。 ? Complete binary tree(完全二叉树) 底层是一个数组,数组内部的数字必须是连续的,不能有空余的内存空间。 ? Binary Search Tree(二叉查找树) 10 /? ? ? 5? ? ? ? 15 ?/? ?? ? ? ?/? ? ? 2? ? ?7? ? ? 12? ? ?20 注意:对于根节点10,必须整个左子树(左子树上的所有节点)都必须比10小,整个右子树(右子树上的所有节点)必须比10大。 同时binary search tree不允许有重复的node; Binary tree 往往是最常见的和recursion结合最紧密的面试题目类型。 理由: 1.每层的node所具备的性质,传递的值和下一层的性质往往一致,比较容易定义recursive rule。 2.base case: null pointer under the leaf node. 3.Example1:int getHeight(Node root) 4.Example2:统计tree里面有多少个node。 ? 常见面试题型: How to get integer value(height) for a problem with size = n? But how? GetHeight of a binary tree? public int getHeight(TreeNode root){ if(root == null){ return 0; } int left = getHeight(root.left); int right = getHeight(root.right); return 1 + Math.max(left,right); ? } Time = O(n); space = O(n) == O(height); ? --------------------------------------------------------------------------------------------------------------------------- Q3:How to determine whether a binary tree is a balanced binary tree? public boolean isBalanced(TreeNode tree){ if(root == null){ return true; } int left = getHeight(root.left); int right = getHeight(root.right); if(Math.abs(left - right) > 1){ return false; } return? isBalanced(root.left) && isBalanced(root.right); } 时间复杂度分析: isBalanced(n/2 + n/2) ?/? getHeight getHeight (n/4 + n/4) (n/4 + n/4) 因为是一个平衡二叉树所以:层数logn? ?So: Time : O(nlogn) --------------------------------------------------------------------------------------------------------------------------- Q4:怎么判断一颗二叉树左右两边是不是对称的? 10 5a? |? ?5b 1a? ?3a? |? ? 3b? ? 1b 2a4a 6a8a? ?|? ? 8b6b? 4b2b ?public boolean isSymmetric(TreeNode noe,TreeNode two){ if(one == null && two == null){ return true; } return false; } if(one.value == two.value){ return false; } return isSymmetric(one.left,two.right) && isSymmetric(one.right,one.left); } Time = O(n); space = O(n) -> O(height)? ?if the tree is balaced -> O(logn) --------------------------------------------------------------------------------------------------------------------------- Q5: (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |