二叉树常见算法

1、二叉树的常见算法：二叉树的定义：/* Definition of TreeNodeauthorZhy*/publicclass TreeNodeint val;TreeNode left;TreeNode right; publicTreeNode(int val) this.val = val;获得二叉树的节点个数：/*method: recursion O(n)System Stack 递归note: root is null : 0;root is not null, return left + right +1;param rootreturn*/publicintgetNumberR

2、ec(TreeNode root) if(root = null) return 0;return getNumberRec(root.left)+getNumberRec(root.right)+1; /*method: Iteration O(n) Queue 迭代paramrootreturn*/publicintgetNum(TreeNode root)if(root = null ) return 0;intnum = 1;LinkedListqueue =new LinkedList(); queue.add(root);while(!queue.isEmpty()TreeNode

3、 cur = queue.removeFirst();if(cur.left!=null) queue.add(cur.left); num+;if(cur.right!=null) queue.add(cur.right); num+;return num;2、获取二叉树的深度/* Method: Recursion O(n)* note: root = null , return 0;* root!=null remember +1;* param root* return*/publicstaticintgetDepthRec(TreeNode root) if(root=null) r

4、eturn 0;return Math.max(getDepthRec(root.left), getDepthRec(root.right)+1; /* Method: Iteration O(n) Queue* param root* return*/publicintgetDepth(TreeNode root)if(root = null) return 0;intdepth = 0;intcurLevelNodes = 1;/ current level nodes numberintnextLevelNodes = 0;/ next level nodes numberLinked

5、Listqueue = new LinkedList(); queue.add(root);while(!queue.isEmpty()TreeNode cur = queue.removeFirst();curLevelNodes -;/ remove one current nodes -if(cur.left!=null)queue.add(cur.left);nextLevelNodes+; if(cur.right!=null) queue.add(cur.right); nextLevelNodes+; if(curLevelNodes=0)/ check if the curre

6、nt level nodes has removed finished depth+;curLevelNodes = nextLevelNodes; nextLevelNodes =0; return depth;3、二叉搜索树转双向链表publicstatic TreeNode BSTTODLL(TreeNode root) if(root=null|(root.left=null&root.right=null) return root; Stackstack = new Stack();TreeNode head = null; TreeNode cur = root; TreeNode

7、 pre = null; while(true) while(cur!=null) stack.push(cur); cur= cur.left; if(stack.isEmpty() break;cur = stack.pop();if(head =null) head = cur;/ 获得头结点 if(pre != null) pre.right = cur; cur.left = pre;pre = cur; cur = cur.right;return head;4、前序遍历/*前序遍历递归* Method: Recursion O(n)* ( 1 )如果二叉树为空，空操作(2)如果二

8、叉树不为空，访问根节点，前序遍历左子树，前序遍历右子 树param root*/ publicvoidpreOrderTraversalRec(TreeNode root)if(root=null) return;System.out.println(root.val+); preOrderTraversalRec(root.left); preOrderTraversalRec(root.right);/* 将二叉树的前序遍历结果存入一个链表中的操作：* Method:recursionnote：当在reOrderRec中重复递归的话，由于每次递归都需要建立一个新 的链表，就会导致内存浪费严

9、重，而且也有问题，所以这时候考虑将链表作为一个参数在一个新的函数中执行添加的 操作param rootreturn*/class Solutionpublic ListpreOrderRec(TreeNode root)Listlist = new ArrayList(); addValue(root,list);return list;publicvoidaddValue(TreeNode root, List list) if(root=null) return;list.add(root.val);addValue(root.left,list);addValue(root.right,

10、list);/*前序遍历迭代* Method:Iteration 通过分析可以得到遍历是先遍历完左子树，再遍历右子 树，可以确定是DFS所以采用Stack首先将右子树放进去，再放左子树；param root*/public ListpreorderTraversal(TreeNode root) Listlist = new ArrayList(); if(root=null) return list;Stackstack = new Stack(); stack.push(root);while(!stack.isEmpty()TreeNode cur = stack.pop(); list

11、.add(cur.val);if(cur.right!=null) stack.push(cur.right); if(cur.left!=null) stack.push(cur.left); return list;/*转变为DLL的思路时间复杂度0(n)空间复杂度0(1)但是改变了树本 身的结构param rootreturn*/publicstatic ArrayListpreorderTraversal(TreeNode root) ArrayListres = new ArrayList(); TreeNode cur = root;TreeNode pre = null; whi

12、le(cur != null)if(cur.left = null) res.add(cur.val); cur = cur.right;else pre = cur.left;/为了得到cur的左子树的最右节点while(pre.right!=null& pre.right!=cur) pre = pre.right;if(pre.right=null)res.add(cur.val);pre.right = cur;cur = cur.left;else/处理的是当pre的right指向cur节点时.断开与cur的连接;pre.right = null;cur = cur.right;re

13、turn res;5、中序遍历/*中序遍历递归Method Recursion( 1 )如果二叉树为空，空操作。* (2)如果二叉树不为空，中序遍历左子树，访问根节点，中序遍历右子 树*/publicvoidinOrderTraversalRec(TreeNode root) if(root=null) return;inOrderTraversalRec(root.left);System.out.println(root.val+); inOrderTraversalRec(root.right);/*中序遍历迭代返回存到一个链表中，操作与上面无差param rootreturn*/pub

14、lic ListinOrderTraversal(TreeNode root) Listlist = new ArrayList(); if(root=null) return list;Stackstack = new Stack(); while(true) while(root!=null)stack.push(root); /将所有的左节点存到栈中 root=root.left;if(stack.isEmpty() break;root = stack.pop(); /左节点为空则取出栈顶元素 list.add(root.val);root= root.right;return lis

15、t;/*转变为DLL的思路时间复杂度0(n)空间复杂度0(1)但是改变了树本 身的结构* param root* return*/publicstatic ListinOrderTraversalMir(TreeNode root)ArrayListlist = new ArrayList();TreeNode cur = root;TreeNode pre = null;while(cur != null)if(cur.left=null)list.add(cur.val);/如果左子树为空，则添加当前节点，并指向右子树cur = cur.right;else/ 左子树不为空，处理左子树pre = cur.lef