做网站的知名公司,淘宝网页版电脑版,河北模板网站建设,站内推广的方式有哪些一、二叉树的基础知识
常见的二叉树类型#xff1a; 满二叉树#xff08;Full Binary Tree#xff09;#xff1a; 只有度为0和度为2的结点#xff0c;且度为0的结点位于最后一层。完全二叉树#xff08;Complete Binary Tree#xff09;#xff1a; 倒数第二层是满二…一、二叉树的基础知识
常见的二叉树类型 满二叉树Full Binary Tree 只有度为0和度为2的结点且度为0的结点位于最后一层。完全二叉树Complete Binary Tree 倒数第二层是满二叉树倒数第一层的结点全部位于左方。二叉搜索树Binary Search Tree 二叉排序树按照左根右的顺序遍历二叉排序树后得到的数组是升序的。平衡二叉搜索树Self-balancing Binary Search Tree AVL树左右两个子树的高度差的绝对值不超过1并且左右两个子树都是一棵平衡二叉树。 二叉树的遍历方法 深度优先遍历Depth First Search使用栈实现 前序遍历中序遍历后序遍历 广度优先遍历Breath First Search使用队列实现 层序遍历
二、深度优先遍历
1. 144【二叉树的前序遍历】
题目 给你二叉树的根节点 root 返回它节点值的前序遍历。代码
方法一递归法
class Solution {public ListInteger preorderTraversal(TreeNode root) {ListInteger ans new LinkedList();preorder(root,ans);return ans;}public void preorder(TreeNode node,ListInteger ans){if(node null) return;ans.add(node.val); //先保存根结点的值再遍历左右子树preorder(node.left,ans);preorder(node.right,ans);}
}方法二迭代法
class Solution {public ListInteger preorderTraversal(TreeNode root) {//使用迭代法对二叉树进行前中后序遍历利用的是栈结构//首先将根入栈因为栈是FILO所以要先将右结点入栈再将左结点入栈ListInteger ans new LinkedList();DequeTreeNode stack new LinkedList();if(root null) return ans;stack.push(root);while (!stack.isEmpty()){TreeNode node stack.pop();ans.add(node.val);if(node.right ! null){stack.push(node.right);}if(node.left ! null){stack.push(node.left);}}return ans;}
}2. 145【二叉树的后序遍历】
题目 给你一棵二叉树的根节点 root 返回其节点值的后序遍历 。代码
方法一递归法
class Solution {public ListInteger postorderTraversal(TreeNode root) {ListInteger ans new LinkedList();postorder(root,ans);return ans;}public void postorder(TreeNode node,ListInteger ans){if(node null) return;postorder(node.left,ans);postorder(node.right,ans);ans.add(node.val);}
}方法二迭代法
class Solution {public ListInteger postorderTraversal(TreeNode root) {//前序遍历返回的ans是根左右如果调换while中右左入栈的顺序//就会得到根右左顺序的ans将ans反转就会得到左右根ListInteger ans new LinkedList();if(root null) return ans;DequeTreeNode stack new LinkedList();stack.push(root);while(!stack.isEmpty()){TreeNode node stack.pop();ans.add(node.val);if(node.left ! null){stack.push(node.left);}if(node.right ! null){stack.push(node.right);}}Collections.reverse(ans);return ans;}
}3. 94【二叉树的中序遍历】
题目 给定一个二叉树的根节点 root 返回它的中序遍历 。代码
方法一递归法
class Solution {public ListInteger inorderTraversal(TreeNode root) {ListInteger ans new LinkedList();inorder(root,ans);return ans;}public void inorder(TreeNode node, ListInteger ans){if(node null) return;inorder(node.left,ans);ans.add(node.val);inorder(node.right,ans);}
}方法二迭代法
class Solution {public ListInteger inorderTraversal(TreeNode root) {//首先判断当前结点是否为空不为空将当前结点的左结点入栈//若为空取栈顶元素加入ans将栈顶元素的右结点作为当前结点//继续重复上面步骤直到当前结点为空且栈为空为止。ListInteger ans new LinkedList();if(root null) return ans;DequeTreeNode stack new LinkedList();TreeNode node root;while (node ! null || !stack.isEmpty()){if(node ! null){stack.push(node);node node.left;}else{node stack.pop();ans.add(node.val);node node.right;}}return ans;}
}三、广度优先遍历
1. 102【二叉树的层序遍历】
题目 给你二叉树的根节点 root 返回其节点值的 层序遍历 。 即逐层地从左到右访问所有节点。代码
class Solution {public ListListInteger levelOrder(TreeNode root) {//二叉树的层序遍历需要利用队列结构//队头元素出队时要将队头元素的左右结点入队//每一层第一个元素出队前队列的长度即为该层的元素个数ListListInteger ans new LinkedList();if(root null) return ans;DequeTreeNode queue new ArrayDeque();queue.offer(root);while (!queue.isEmpty()){ListInteger temp new LinkedList();int len queue.size();while (len0){TreeNode node queue.poll();temp.add(node.val);if(node.left ! null){queue.offer(node.left);}if(node.right ! null){queue.offer(node.right);}len--;}ans.add(temp);}return ans;}
}2. 107【二叉树的层次遍历II】
题目 给你二叉树的根节点 root 返回其节点值 自底向上的层序遍历 。 即按从叶子节点所在层到根节点所在的层逐层从左向右遍历代码
class Solution {public ListListInteger levelOrderBottom(TreeNode root) {//将上一题的结果反转即可ListListInteger ans new LinkedList();if(root null) return ans;DequeTreeNode queue new ArrayDeque();queue.offer(root);while (!queue.isEmpty()){int len queue.size();ListInteger temp new LinkedList();while (len 0){TreeNode node queue.poll();temp.add(node.val);if(node.left ! null){queue.offer(node.left);}if(node.right ! null){queue.offer(node.right);}len--;}ans.add(temp);}Collections.reverse(ans);return ans;}
}3. 199【二叉树的右视图】
题目 给定一个二叉树的 根节点 root想象自己站在它的右侧按照从顶部到底部的顺序返回从右侧所能看到的节点值。代码
class Solution {public ListInteger rightSideView(TreeNode root) {ListInteger ans new LinkedList();if(root null) return ans;DequeTreeNode queue new ArrayDeque();queue.offer(root);while(!queue.isEmpty()){int len queue.size();TreeNode node;while (len 0){node queue.poll();if(node.left ! null){queue.offer(node.left);}if(node.right ! null){queue.offer(node.right);}if(len 1){ans.add(node.val);}len--;}}return ans;}
}4. 637【二叉树的层平均值】
题目 给定一个非空二叉树的根节点 root , 以数组的形式返回每一层节点的平均值。与实际答案相差 1 0 − 5 10^{-5} 10−5以内的答案可以被接受。代码
class Solution {public ListDouble averageOfLevels(TreeNode root) {ListDouble avg new LinkedList();DequeTreeNode queue new ArrayDeque();queue.offer(root);while(!queue.isEmpty()){int len queue.size();double sum 0;for (int i 0; i len; i) {TreeNode node queue.poll();sum node.val;if(node.left ! null){queue.offer(node.left);}if(node.right ! null){queue.offer(node.right);}}avg.add(sum/len);}return avg;}
}5. 429【N叉树的层序遍历】
题目 给定一个 N 叉树返回其节点值的层序遍历。即从左到右逐层遍历。树的序列化输入是用层序遍历每组子节点都由 null 值分隔。代码
class Solution {public ListListInteger levelOrder(Node root) {ListListInteger ans new LinkedList();if(root null) return ans;DequeNode queue new ArrayDeque();queue.offer(root);while(!queue.isEmpty()){int len queue.size();ListInteger temp new LinkedList();for (int i 0; i len; i) {Node node queue.poll();temp.add(node.val);for (int j 0; j node.children.size(); j) {queue.offer(node.children.get(j));}}ans.add(temp);}return ans;}
}6. 515【在每个树行中找最大值】
题目 给定一棵二叉树的根节点 root 请找出该二叉树中每一层的最大值。代码
class Solution {public ListInteger largestValues(TreeNode root) {ListInteger ans new LinkedList();if(root null) return ans;DequeTreeNode queue new ArrayDeque();queue.offer(root);while(!queue.isEmpty()){int len queue.size();int max queue.peek().val;while (len 0){TreeNode node queue.poll();if(node.left ! null){queue.offer(node.left);}if(node.right ! null){queue.offer(node.right);}max max node.val ? max : node.val;len--;}ans.add(max);}return ans;}
}7. 116【填充每个节点的下一个右侧节点指针】
题目 给定一个完美二叉树其所有叶子节点都在同一层每个父节点都有两个子节点。二叉树定义如下
struct Node {int val;Node *left;Node *right;Node *next;
}填充它的每个 next 指针让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点则将 next 指针设置为 NULL。初始状态下所有 next 指针都被设置为 NULL。
代码
class Solution {public Node connect(Node root) {if(root null)return null;DequeNode queue new ArrayDeque();queue.offer(root);while (!queue.isEmpty()){int len queue.size();for (int i 0; i len; i) {Node temp queue.poll();if(temp.left ! null){queue.offer(temp.left);}if(temp.right ! null){queue.offer(temp.right);}if(i len-1){temp.next null;}else {temp.next queue.peek();}}}return root;}
}8. 117【填充每个节点的下一个右侧节点指针II】
题目 该题题目与上一题只差了一个完美二叉树但是代码是一样的这里为了节省空间就不再放一遍了。
9. 104【二叉树的最大深度】
题目 给定一个二叉树 root 返回其最大深度。二叉树的最大深度是指从根节点到最远叶子节点的最长路径上的节点数。代码
class Solution {public int maxDepth(TreeNode root) {if(root null) return 0;DequeTreeNode queue new ArrayDeque();queue.offer(root);int height 0;while (!queue.isEmpty()){int len queue.size();for (int i 0; i len; i) {TreeNode temp queue.poll();if(temp.left ! null){queue.offer(temp.left);}if(temp.right ! null){queue.offer(temp.right);}}height;}return height;}
}10. 111【二叉树的最小深度】
题目 给定一个二叉树找出其最小深度。最小深度是从根节点到最近叶子节点的最短路径上的节点数量。说明叶子节点是指没有子节点的节点。代码
class Solution {public int minDepth(TreeNode root) {//当遍历到最小深度时必有一个叶子结点if(root null) return 0;DequeTreeNode queue new ArrayDeque();queue.offer(root);int height 0;boolean isFlag false;while (!queue.isEmpty()){int len queue.size();height;for (int i 0; i len; i) {TreeNode temp queue.poll();if(temp.left null temp.right null){isFlag true;break;}if(temp.left ! null){queue.offer(temp.left);}if(temp.right ! null){queue.offer(temp.right);}}if(isFlag) return height;}return height;}
}
