Recover Binary Search Tree Two elements of a binary search tree (BST) are swapped by mistake. 递归法 思路 这道题是要求恢复一颗有两个元素调换错了的二叉查找树。中序遍历BST 然后找到逆序。有两种情况需要考虑: 两个错位的节点是相邻的父子树关系, 那么找到第一个先序遍历逆序的两个节点 两个错位的节点不是父子...

Given a binary tree, determine if it is a valid binary search tree(BST). Assume a BST is defined as follows: The left subtree of a node contains only nodes with keys less than thenode's key. The right subtree of a node contains only nodes with keysgreater than the node's key. Both the left and ri...

{代码...} 递归法 思路 相当于一次先序遍历, 将先访问的点存储在数组里, 下一个访问的节点为之前访问的点的右子树 复杂度 时间O(n)。空间上是栈的大小，O(logn) 代码 {代码...} 非递归解法 思路 对于一个节点我们把右子树入栈, 左子树放在右边. 如果左子树没有了我们就把栈内最近的节点拿出来作为节点的右子树 复杂度 时...

Populating Next Right Pointers in Each Node {代码...} 广度优先搜索 思路 相当于层序遍历BST, 只是除了每层的最后一个节点其他节点都要给一个next指针指向队列里的下一个节点. 此方法I &II都适用 复杂度 时间O(n) 空间O(n) 代码 public void connect(TreeLinkNode root) { {代码...} 递归解法 思路 node的left ch...

所以这道题可以用递归的方法解决。通过先序遍历找到第一个点作为根节点，在中序遍历中找到根节点并记录index。此处用hashmap来存储, key为中序遍历节点值 value为index因为中序遍历中根节点左边为左子树，所以可以记录左子树的长度并在先序遍历中依据这个长度找到左子树的区间，用同样方法可以找到右子树的区间。递归的...

数组的中点为根, 然后递归中点为界限的左边和右边的数组. 递归的写法跟常规稍有不同，就是要把根root先new出来，然后它的左节点接到递归左边部分的返回值，右节点接到递归右边部分的返回值，最后将root返回回去。这个模板在树的构造中非常有用.

Binary Tree Paths Given a binary tree, return all root-to-leaf paths. {代码...} 深度优先搜索 复杂度 时间O(n) 空间栈O(n logn) 代码 {代码...}

Given a binary tree containing digits from 0-9 only, each root-to-leafpath could represent a number. An example is the root-to-leaf path 1->2->3 which represents thenumber 123. Find the total sum of all root-to-leaf numbers. For example, {代码...} Return the sum = 12 + 13 = 25.

Given a binary tree, find the maximum path sum. For this problem, a path is defined as any sequence of nodes from somestarting node to any node in the tree along the parent-childconnections. The path does not need to go through the root. For example: Given the below binary tree, {代码...}

Given a binary tree and a sum, determine if the tree has aroot-to-leaf path such that adding up all the values along the pathequals the given sum. For example: Given the below binary tree and sum = 22, {代码...}

Given two binary trees, write a function to check if they are equal ornot. Two binary trees are considered equal if they are structurallyidentical and the nodes have the same value.

Given a binary tree, find its minimum depth. The minimum depth is the number of nodes along the shortest path fromthe root node down to the nearest leaf node.

时间O(n), 空间O(logn) 因为在遍历过程中，栈中最多会存储从root到最深的leave这一条path上的全部node，即树高O(lgn)