春节7天练 | Day 5：二叉树和堆

// 翻转二叉树 public TreeNode invertTree(TreeNode root) { if(root == null){ return root; } TreeNode node = root; Queue<TreeNode> queue = new LinkedList<>(); queue.add(node); while(!queue.isEmpty()){ node = queue.poll(); TreeNode tempNode = node.left; node.left = node.right; node.right = tempNode; if(node.left != null){ queue.offer(node.left); } if(node.right != null){ queue.offer(node.right); } } return root; } // 二叉树的最大深度 public int maxDepth(TreeNode root) { if(root == null) return 0; return Math.max(maxDepth(root.left), maxDepth(root.right))+1; } // 验证二叉查找树 public boolean isValidBST(TreeNode root) { if (root == null) { return true; } Stack<TreeNode> stack = new Stack<>(); TreeNode node = root; TreeNode preNode = null; while(node != null || !stack.isEmpty()){ stack.push(node); node = node.left; while(node == null && !stack.isEmpty()){ node = stack.pop(); if(preNode != null){ if(preNode.val >= node.val){ return false; } } preNode = node; node = node.right; } } return true; } // 路径总和 public boolean hasPathSum(TreeNode root, int sum) { if (root == null) { return false; } return hasPathSum(root, root.val, sum); } public boolean hasPathSum(TreeNode root, int tmp, int sum) { if (root == null) { return false; } if (root.left == null && root.right == null) { return tmp == sum; } if (root.left == null) { return hasPathSum(root.right, root.right.val + tmp, sum); } if (root.right == null) { return hasPathSum(root.left, root.left.val + tmp, sum); } return hasPathSum(root.left, root.left.val + tmp, sum) || hasPathSum(root.right, root.right.val + tmp, sum); }

作者可以提供pdf版的课程资料吗，不然我觉得不值，因为不能大量复制，不能形成书面笔记，毕竟我付费了。

Golang max depth /** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func maxDepth(root *TreeNode) int { if root == nil { return 0 } if root.Left == nil && root.Right == nil { return 1 } return int(math.Max(float64(maxDepth(root.Left)), float64(maxDepth(root.Right)))) + 1 }

王争老师新年的第五天快乐！ 放上今天LeetCode四题的代码和思路 解题思路：对于树，这个结构很特殊，树是由根节点，根节点的左子树，根节点的右子树组成的，定义的时候就是一个递归的定义。因此在解决与树相关的问题的时候，经常会用到递归。今天的四题都不例外。 翻转二叉树：就是递归的让节点的左子树指向右子树，右子树指向左子树。 二叉树的最大深度：当前深度=1+Max(左子树深度，右子树深度)，递归的结束条件为节点为null，或者是一个叶节点。 验证二叉查找树：一颗树是二叉查找树必须满足：当前的节点>=左子树&&当前的节点<=右子树，左子树是二叉查找树，右子树是二叉查找树，也是递归的定义。 路径总和：遍历树的路径，看是否和为sum值（树的遍历也是递归的哦） 四道题的代码在：https://github.com/yyxd/leetcode/tree/master/src/leetcode/tree

平衡树的各种操作太烧脑了，左旋右旋，红黑树就更别提了。过段时间就忘。😢

树的前中后序遍历-递归实现： public class TreeTraversal { public static class Node { public int value; public Node left; public Node right; public Node(int value) { this.value = value; } } // 二叉树的递归遍历 public static void preOrderRecursive(Node head) { if (head == null) { return; } System.out.print(head.value + " "); preOrderRecursive(head.left); preOrderRecursive(head.right); } public static void inOrderRecursive(Node head) { if (head == null) { return; } inOrderRecursive(head.left); System.out.print(head.value + " "); inOrderRecursive(head.right); } public static void postOrderRecursive(Node head) { if (head == null) { return; } postOrderRecursive(head.left); postOrderRecursive(head.right); System.out.print(head.value + " "); } }

树的前中后序遍历-非递归实现： import java.util.Stack; public class TreeTraversal { public static class Node { public int value; public Node left; public Node right; public Node(int value) { this.value = value; } } // 二叉树的非递归遍历 public static void preOrder(Node head) { System.out.print("pre-order: "); if (head == null) { return; } Stack<Node> s = new Stack<>(); s.push(head); while (!s.isEmpty()) { head = s.pop(); System.out.print(head.value + " "); if (head.right != null) { s.push(head.right); } if (head.left != null) { s.push(head.left); } } System.out.println(); } public static void inOrder(Node head) { System.out.print("in-order: "); if (head == null) { return; } Stack<Node> s = new Stack<>(); while (!s.isEmpty() || head != null) { if (head != null) { s.push(head); head = head.left; } else { head = s.pop(); System.out.print(head.value + " "); head = head.right; } } System.out.println(); } public static void postOrder(Node head) { System.out.print("pos-order: "); if (head == null) { return; } Stack<Node> tmp = new Stack<>(); Stack<Node> s = new Stack<>(); tmp.push(head); while(!tmp.isEmpty()) { head = tmp.pop(); s.push(head); if (head.left != null) { tmp.push(head.left); } if (head.right != null) { tmp.push(head.right); } } while (!s.isEmpty()) { System.out.print(s.pop().value + " "); } System.out.println(); } }

二叉查找树节点删除逻辑，不知道对不对： public boolean removeNode(int val) { if (null == root) { return false; } if (root.val == val) { // 根节点 root = replace(root); } else { Node parent = findParent(val); if (null == parent) { return false; } if (parent.left.val == val) { parent.left = replace(parent.left); } else if (parent.right.val == val) { parent.right = replace(parent.right); } } return true; } private Node replace(Node cur) { Node res = null; if (cur.left != null && cur.right != null) { res = cur.left; res.left = replace(cur.left); res.right = cur.right; } else if (cur.left != null) { res = cur.left; } else if (cur.right != null) { return cur.right; } // 置空 cur.left = null; cur.right = null; return res; }

java实现二叉树前序、中序、后序和层次遍历 代码如下： package tree; import java.util.LinkedList; import java.util.Queue; public class BinaryTree { private Node root = null; public static class Node { private String data; private Node left; private Node right; public Node(String data, Node left, Node right) { this.data = data; this.left = left; this.right = right; } } public void preOrder(Node root) { if (null == root) { return ; } System.out.print(root.data + " "); preOrder(root.left); preOrder(root.right); } public void inOrder(Node root) { if (null == root) { return ; } inOrder(root.left); System.out.print(root.data + " "); inOrder(root.right); } public void postOrder(Node root) { if (null == root) { return ; } postOrder(root.left); postOrder(root.right); System.out.print(root.data + " "); } public void traverseByLayer(Node root) { if (null == root) { return ; } Queue<Node> queue = new LinkedList<Node>(); queue.add(root); while (!queue.isEmpty()) { Node pNode = queue.peek(); System.out.print(pNode.data + " "); queue.poll(); if (root.left != null) { queue.add(root.left); } if (root.right != null) { queue.add(root.right); } } } }

今天看了一下这一节的题目，发现校招面试的时候都考过，今天又刷了一下，总结了一波，相应的知识点也总结了一下~