二叉树 二叉树遍历
前序:根节点 => 左子树 => 右子树
中序:左子树 => 根节点 => 右子树
后序:左子树 => 右子树 => 根节点
层序:按照每层的节点进行遍历
通过遍历序列获取树结构:前、后、层序都能确定顶部节点,中序能够根据顶部节点确定左右子树,所以通过遍历序列获取树结构时必须要有前、后、层三者之一,以及中序序列
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 // 前序、中序、后序遍历,调整内部函数的递归顺序即可。示例为后序 function orderTraversal( root ) { // write code here let result = [] function traversal(node){ if(node == null) return traversal(node.left) traversal(node.right) result.push(node.val) } afterTraversal(root) return result } // 层级遍历 function levelOrder(root) { let result = []; let dfs = (root, index) => { if (!root) { return; } if (!result[index]) { result[index] = []; } result[index].push(root.val); dfs(root.left, index + 1); dfs(root.right, index + 1); }; dfs(root, 0); return result; } // 序列化二叉树 function TreeNode(x) { this.val = x; this.left = null; this.right = null; } function Serialize(pRoot, arr = []) { // write code here if (!pRoot) { arr.push("#"); return arr; } else { arr.push(pRoot.val); Serialize(pRoot.left, arr); Serialize(pRoot.right, arr); } return arr; } function Deserialize(s) { // write code here let arr = let a = arr.shift(); let node = null; if (typeof a === "number") { node = new TreeNode(a); node.left = Deserialize(arr); node.right = Deserialize(arr); } return node; } module.exports = { Serialize: Serialize, Deserialize: Deserialize, };
二叉树的操作也是基于上述遍历进行运算。
二叉搜索树转双向链表 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 // 利用栈,非常巧妙的完成了较小节点的暂存 function Convert(pRootOfTree) { // write code here if(!pRootOfTree) return null let stack = [],p = pRootOfTree,pre = null,isFirst = true while(p||stack.length>0){ while(p){ stack.push(p) p = p.left } p = stack.pop() if(isFirst){ pRootOfTree = p pre = pRootOfTree isFirst = false }else{ pre.right = p p.left = pre pre = p } p = p.right } return pRootOfTree }
二叉树的特殊类型 二叉搜索树:左侧子树的值都小于根节点的值,右侧子树的值都大于根节点的值
完全二叉树:除二叉树叶子节点层,所有层都没有空缺节点,且叶子节点从左到右连续没有空缺
平衡二叉树:是空树或者左右子树的高度差绝对值不超过1,且左右子树都是平衡二叉树
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 // 判断二叉搜索树 const helper = (root, lower, upper) => { if (root === null) { return true; } if (root.val <= lower || root.val >= upper) { return false; } return helper(root.left, lower, root.val) && helper(root.right, root.val, upper); } var isValidBST = function(root) { return helper(root, -Infinity, Infinity); }; // 判断完全二叉树 function isCompleteTree( root ) { // write code here if(root == null) return true; const queue = []; queue.push(root); let flag = false; while(queue.length) { const node = queue.shift(); if(node == null) { flag = true; continue; } if(flag == true) { return false; } queue.push(node.left); queue.push(node.right); } return true; } // 判断平衡二叉树 function IsBalanced_Solution(pRoot) { if(!pRoot) return true; // write code here return (Math.abs(getMaxDepth(pRoot.left) - getMaxDepth(pRoot.right)) <=1) && IsBalanced_Solution(pRoot.left) && IsBalanced_Solution(pRoot.right) } function getMaxDepth(root) { if(!root) return 0; return Math.max(getMaxDepth(root.left)+1,getMaxDepth(root.right)+1) }