算法笔记链表二叉树递归和二叉树
nancy Jane写了几个程度为简单的二叉树题目,都是和递归有关
二叉树是一种常见的树状数据结构,其中每个节点最多有两个子节点,分别称为左子节点和右子节点。二叉树的每个节点包含一个值以及指向其左右子节点的指针。以下是二叉树的一些基本概念:
- 根节点(Root):二叉树的顶部节点,没有父节点的节点。
- 叶子节点(Leaf):没有子节点的节点称为叶子节点,即左右子节点都为空的节点。
- 内部节点(Internal Node):有至少一个子节点的节点称为内部节点。
- 子树(Subtree):二叉树中的任意节点和其所有后代节点,形成的结构称为子树。
- 深度(Depth):从根节点到某个节点的唯一路径的边数。
- 高度(Height):从某个节点到其最远叶子节点的路径的边数,也可以理解为该节点所在子树的深度。
二叉树有多种不同的类型,包括但不限于:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
| var inorderTraversal = function (root) { const arr = [] function traverse(root){ if(root==null) return traverse(root.left) arr.push(root.val) traverse(root.right) } traverse(root) return arr };
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
| var maxDepth = function (root) { function comDepth(root){ if(root===null){ return 0 }else{ const leftDepth=comDepth(root.left) const rightDepth=comDepth(root.right) return Math.max(leftDepth,rightDepth)+1 } } return comDepth(root)
};
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
| var invertTree = function (root) {
function reverse(root) { if (root == null) { return null } const left = reverse(root.left) const right = reverse(root.right) root.left = right root.right = left return root } return reverse(root) };
|
if语句里的return语句直接return是因为这个return语句处于一个递归函数内部。在递归函数内部,当满足某个条件时(比如节点为空),递归函数可以直接返回,这意味着递归的结束。
遇到空节点不能结束的行为需要指定return的值
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
| var isSymmetric = function (root) { function isSymmetric(root){ function isMirror(left,right) { if (left == null && right == null) { return true } if(left==null||right==null){ return false } if(left.val!==right.val){ return false } return isMirror(left.left,right.right)&&isMirror(left.right,right.left) } return isMirror(root,root) } return isSymmetric(root) };
|
有序数组转换为二叉搜索树
1 2 3 4 5 6 7 8 9 10 11 12 13 14
| var sortedArrayToBST = function (nums) { function sortTree(nums) { if (!nums.length) { return null } let mid = Math.floor(nums.length / 2) let root = new TreeNode(nums[mid]) root.left = sortTree(nums.slice(0, mid)) root.right = sortTree(nums.slice(mid + 1)) return root } return sortTree(nums) };
|