leetcode Tree 整理版

本次题解为 leetcode tree 的整理,包括

  • 依照leetcode定义 自己写的createTree方法,便于测试中序遍历的下标和
  • 94 Binary Tree Inorder Traversal
  • 95 Unique Binary Search Trees II
  • 96 Unique Binary Search Trees
  • 98 Validate Binary Search Tree
  • 99 Recover Binary Search Tree
  • 100 Same Tree
  • 101 Symmetric Tree
  • 102 Binary Tree Level Order Traversal
  • 103 Binary Tree Zigzag Level Order Traversal
  • 104 Maximum Depth of Binary Tree
  • 105 Construct Binary Tree from Preorder and Inorder Traversal
  • 106 Construct Binary Tree from Inorder and Postorder Traversal
  • 107 Binary Tree Level Order Traversal II
  • 108 Convert Sorted Array to Binary Search Tree
  • 109 Convert Sorted List to Binary Search Tree
  • 110 Balanced Binary Tree
  • 111 Minimum Depth of Binary Tree
  • 112 Path Sum
  • 113 Path Sum II
  • 114 Flatten Binary Tree to Linked List
  • 116 Populating Next Right Pointers in Each Node
  • 117 Populating Next Right Pointers in Each Node II
  • 124 Binary Tree Maximum Path Sum
  • 129 Sum Root to Leaf Numbers
  • 144 Binary Tree Preorder Traversal
  • 145 Binary Tree Postorder Traversal
  • 173 Binary Search Tree Iterator
  • 199 Binary Tree Right Side View
  • 222 Count Complete Tree Nodes
  • 226 Invert Binary Tree
  • 230 Kth Smallest Element in a BST
  • 235 Lowest Common Ancestor of a Binary Search Tree
  • 236 Lowest Common Ancestor of a Binary Tree
  • 257 Binary Tree Paths
  • 297 Serialize and Deserialize Binary Tree
  • 449. Serialize and Deserialize BST

 

1.首先是leetcode对于树的表示方法:

OJ’s Binary Tree Serialization:

The serialization of a binary tree follows a level order traversal, where ‘#’ signifies a path terminator where no node exists below.

Here’s an example:

The above binary tree is serialized as "{1,2,3,null,null,4,null,null,5}".

树结点表示为:

我的建树方法见297题 Serialize and Deserialize Binary Tree的方法一

2.题解归类

1.构建树

  • 用前序和中序建树105
  • 用后序和中序建树106
  • 数组构建BST 108
  • 链表构建BST 109

2.树的遍历

  • 前序 144
  • 中序 94
  • 后序 145
  • 层次 102 103 107

3.树的属性

  • 求深度 104
  • 是否平衡是平衡树 110
  • 最小深度 111

4.BST树

  • 判断BST是否合法 98
  • 恢复BST 99
  • BST实现迭代:173(用到某一遍历)

 

3.题解代码(按题号顺序)

94. Binary Tree Inorder Traversal

Given a binary tree, return the inorder traversal of its nodes’ values.

For example:
Given binary tree {1,#,2,3},

return [1,3,2].

题目地址:leetcode 94 Binary Tree Inorder Traversal

题意:给定一棵树,求它的中序遍历。

思路:中序遍历和前序、后序不同地方在于是先输出左子结点然后根结点,最后右子结点。

递归版本很好理解。

非递归版本先将所有左子树入栈,之后将所有右子树的左子树入栈。(看代码吧~)

 

Python

Python非递归版本

 


 

95. Unique Binary Search Trees II

Given n, generate all structurally unique BST’s (binary search trees) that store values 1…n.

For example,
Given n = 3, your program should return all 5 unique BST’s shown below.

题目地址:leetcode Unique Binary Search Trees II

题目大意:给定n,求1~n共n个数,能组成几棵不一样的BST,建立这些树并且返回所有不同BST的根结点。

思路:

分治,对于1~n这n个数,都有可能成为根结点。枚举1~n,对于 1<=i<=n,有i的左结点为[1,i-1]  (i-1 >=1),右结点是[i+1,n] i+1 <=n

递归的获取左右子结点,然后只需要建立根结点,使根结点的左右子结点指向获取的左右子结点即可。

C++

 

Python

 

 

 

96. Unique Binary Search Trees

Given n, how many structurally unique BST’s (binary search trees) that store values 1…n?

For example,
Given n = 3, there are a total of 5 unique BST’s.

 

题目大意:给定n,求1~n共n个数,能组成几棵不一样的BST

思路:

可以类似95题写dfs+记忆化搜索

也可以写成非递归的形式:

设dp[n]为n个数组成的不同BST总数。

如果左儿子个数为j,有儿子显然为n-1-j个,那么总共显然有 dp[j] * dp[n-1-j]种

故枚举j从0~n-1然后相加既可。

C++

Python

 

 

98. Validate Binary Search Tree

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 the node’s key.
  • The right subtree of a node contains only nodes with keys greater than the node’s key.
  • Both the left and right subtrees must also be binary search trees.

题目地址:leetcode 98 Validate Binary Search Tree

题意:给定一棵BST,判断其是否合法。合法需要满足:

  • 根结点大于左子树结点, 根结点小于右子树结点。
  • 左右子树是合法的BST

思路:

  1. 递归判断左右子树。需要用出现过的最大、最小值来判断。 如左子树最大值不可能超过根,右子树最小值不可能小于根
  2. 中序遍历。 合法的BST中序遍历必为有序序列。

方法一

C++

Python

方法二

C++

Python

 

 

99. Recover Binary Search Tree

Two elements of a binary search tree (BST) are swapped by mistake.

Recover the tree without changing its structure.

Note:
A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?

题目地址:leetcode 99 Recover Binary Search Tree

题意:一棵BST中有两个元素被调换了,求在不破坏BST情况下,将其恢复。

思路:对于此问题,关键是要找到被调换的两个元素。我们知道,对于中序遍历,合法的BST数必为有序,故进行中序遍历,如果pre.val >root.val说明有误。注意区分第一次和第二次,标记即可。

C++

 

Python

 

 

100. Same Tree

Given two binary trees, write a function to check if they are equal or not.

Two binary trees are considered equal if they are structurally identical and the nodes have the same value.

题目地址:leetcode Same Tree

题目大意:给定两棵树,判断他们是否相等(结构和值都相等)

思路:递归判断即可。

C++

Python

 

 

101. Symmetric Tree

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree is symmetric:

But the following is not:

Note:
Bonus points if you could solve it both recursively and iteratively.

题目地址:leetcode Symmetric Tree

题目大意:给定一棵树,判断它是否关于root对称。

思路:继续递归吧。。。水

C++

Python

还可以用BFS的方式做:

 

 

 

102. Binary Tree Level Order Traversal

Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).

For example:
Given binary tree {3,9,20,#,#,15,7},

return its level order traversal as:

题目地址:leetcode Binary Tree Level Order Traversal

题目大意:给定一棵树,返回其层次遍历

思路:

方法一: 用队列进行层次遍历

C++

Python

方法二 先序遍历

 

 

 

 

103. Binary Tree Zigzag Level Order Traversal

Given a binary tree, return the zigzag level order traversal of its nodes’ values. (ie, from left to right, then right to left for the next level and alternate between).

For example:
Given binary tree {3,9,20,#,#,15,7},

return its zigzag level order traversal as:

题目地址:leetcode Binary Tree Zigzag Level Order Traversal

题目大意:给定一棵树,返回其层次遍历(要求第一行从左到右,第二行从右到左)

思路:和上面一题差不多,加个判断奇偶即可。

C++

Python

当然还可以不逆序,直接输出到对应位置

 

 

 

 

104. Maximum Depth of Binary Tree

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

题目地址:leetcode Maximum Depth of Binary Tree

题目大意:给定一棵树,返回其最大深度。

思路:思路,dfs.

C++

另一种更简洁写法

 

Python

 

 

105 . Construct Binary Tree from Preorder and Inorder Traversal

Given preorder and inorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

 

题目地址:leetcode 105 Construct Binary Tree from Preorder and Inorder Traversal

题意:给定一棵树的前序和中序遍历,构建这棵树

思路:以下面的例子为例:

前序遍历为: 3,9,20,15,7

中序遍历为: 9,3,15,20,7

前序遍历的第一个一定是根结点,而中序遍历的根结点把树准确的分为左子树和右子树。

所以,在中序遍历中查找3,发现下标为1,那么[0,1)为左子树,[2,5)为右子树。

递归的往下查找即可。

可以写出简洁的code

不过这样每次都需要切片,效率比较低。

我们可以设前序遍历开始为pb,结束pe,中序遍历开始为ib,结束为ie。前序遍历的第pb个元素(即当前根结点)在中序遍历中下标为index

则长度为len = index – ib

那么有,

  • 左子树,每次递归的下标为:[pb + 1, pb + len + 1)   [ ib, ib+len)
  • 右子树:[pb + len + 1, pe)  [ib + len + 1, ie)

Python

C++

 

 

106. Construct Binary Tree from Inorder and Postorder Traversal

Given inorder and postorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

 

题目地址:leetcode 106 Construct Binary Tree from Inorder and Postorder Traversal

题意:给定一棵树的中序和后序遍历,构建这棵树。

思路:

思路:以下面的例子为例:

后序遍历为: 9,15,7,20,3

中序遍历为: 9,3,15,20,7

后序遍历的最后一个一定是根结点,而中序遍历的根结点把树准确的分为左子树和右子树。

和105题差不多,我们可以看出:

 

我们可以设后序遍历开始为pb,结束pe,中序遍历开始为ib,结束为ie。前序遍历的第pb个元素(即当前根结点)在中序遍历中下标为index

则长度为len = index – ib

那么有,

  • 左子树,每次递归的下标为:[pb,  pb + len)   [ ib, ib+len)
  • 右子树:[pb + len, pe – 1)  [ib + len + 1, ie)

可以看出中序遍历的下标和上面一题是一样的

Python

C++

 

 

107. Binary Tree Level Order Traversal II

Given a binary tree, return the bottom-up level order traversal of its nodes’ values. (ie, from left to right, level by level from leaf to root).

For example:
Given binary tree {3,9,20,#,#,15,7},

return its bottom-up level order traversal as:

 

题目地址:leetcode Binary Tree Level Order Traversal II

题目大意:给定一棵树,返回其层次遍历的逆序。

思路:和102题其实一样,最后结果逆序即可。太水了

C++

 

Python

还可以DFS做

 

 

108. Convert Sorted Array to Binary Search Tree

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

题目地址:leetcode 108 Convert Sorted Array to Binary Search Tree

题意:给定一个排好序的数组,要求建造BST树(高度要平衡)

思路:每次二分,递归建立左右子树

C++

Java

Python

 

 

109 Convert Sorted List to Binary Search Tree

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

 

题目地址:leetcode 109 Convert Sorted List to Binary Search Tree

题意:给定一个排好序的链表,要求建造BST树(高度要平衡)

思路:

方法一

每次将链表分为左右两部分即可。

  • 使用快慢指针
  • 复杂度O(nlogn)

C++

Java

Python

之前的python,计数的,不如快慢指针优雅。

方法二

BST利用中序遍历为有序的性质,来建树。

  • 相当于链表保存的为中序遍历
  • 要让建出来的树尽可能的平衡,那么用二分,mid = (L + R)/2,左边的就是[L,mid-1],右边[mid+1,R]
  • 中序遍历先遍历左子树,保存全局的链表head指针,每次向后移动即可。

C++

 

Java

 

Python

 

 

 

110. Balanced Binary Tree

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

题目地址:leetcode Balanced Binary Tree

题目大意:给定一棵树,判断其是否是平衡树(要求左右子树高度差不能超过1)

思路:用DFS来计算高度,若高度差超过1,则返回-1.否则,返回高度。

C++

 

Python

 

 

 

111. Minimum Depth of Binary Tree

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

题目地址:leetcode Minimum Depth of Binary Tree

题目大意:给定二叉树,求其最小的高度。(从根结点到叶结点的距离)

思路:DFS。注意叶结点的判断。

C++

Python

 

 

 

112. Path Sum

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

For example:
Given the below binary tree and sum = 22,

return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

题目地址:leetcode Path Sum

题目大意:给定一棵树,判断是否有从根结点到叶结点和为sum的情况。

思路:继续深搜。。

C++

Python

 

 

 

113. Path Sum II

Given a binary tree and a sum, find all root-to-leaf paths where each path’s sum equals the given sum.

For example:
Given the below binary tree and sum = 22,

return

题目地址:leetcode Path Sum II

题目大意:给定二叉树,要求返回其和为sum的所有路径

思路:DFS。。。

C++

 

Python

也可以这么写

 

 

114. Flatten Binary Tree to Linked List

Given a binary tree, flatten it to a linked list in-place.

For example,
Given

The flattened tree should look like:

Hints:

If you notice carefully in the flattened tree, each node’s right child points to the next node of a pre-order traversal.

题目地址:leetcode Flatten Binary Tree to Linked List

题目大意:给定一棵二叉树,要求将其变为一条链(按照前序遍历的顺序)

思路:递归,设root左右子结点为L和R,把L和R分别变为链,L最后一个元素指向R即可。

C++

Python

 

 

116.  117 Populating Next Right Pointers in Each Node

Given a binary tree

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

Note:

  • You may only use constant extra space.
  • You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).

For example,
Given the following perfect binary tree,

After calling your function, the tree should look like:

题目地址:

题意:给定一棵树,要求将其每一层的子结点连接起来。

思路:117比116的区别在于,116是满二叉树,117不一定。

一个思路是层次遍历,这样不管是不是满二叉树,都不会错,但是空间并不是O(1)的

 

 

有没有其他的方法呢?

我们先来看看116题,对于满二叉树,我们每次遍历一层的时候,将左儿子的next设置为右儿子,将右儿子设置为兄弟节点的左儿子。

C++

Python

那么117题并不是满二叉树,这就需要另外一个指针,指向每一层的最左边的节点,然后父节点不断的遍历其兄弟节点,而该节点对next赋值并不断的移动到刚赋值的next节点即可。

C++

Python

可用如下代码检验此题

 

 

124. Binary Tree Maximum Path Sum

Given a binary tree, find the maximum path sum.

The path may start and end at any node in the tree.

For example:
Given the below binary tree,

Return 6.

题目地址:leetcode Binary Tree Maximum Path Sum

题意:给定一棵二叉树,要求返回其路径中和最大值。(可以从任意起点开始到任意起点结束)

思路:DFS,设dfs(root)返回的是包括root这个结点的单一路径上的最大值。设L=dfs(root.left) ,R=dfs(root.right)如题目样例中的{1,2,3,}就是L=2,R=3

则可能的结果有:

  • L+R+root.val (左右子树和根构成路径为最大值,就是题目的情况)
  • max(L,R) + root.val(左或者右子树和根构成最大值)
  • root.val本身为最大值

和全局变量ans比较更新即可。

需要注意的是dfs返回值,可能是

  • max(L,R) + root.val 某一条路径
  • root.val  只是该结点(下面都是负的了)

Python

 

 

129. Sum Root to Leaf Numbers

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.

An example is the root-to-leaf path 1->2->3 which represents the number 123.

Find the total sum of all root-to-leaf numbers.

For example,

The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.

Return the sum = 12 + 13 = 25.

题目地址:leetcode 129 Sum Root to Leaf Numbers

题意:给定一棵仅由数字0~9组成的二叉树,求根到叶子结点各个路径数字组成的字符串之和

思路:继续DFS

Python

C++

 

 

144. Binary Tree Preorder Traversal

Given a binary tree, return the preorder traversal of its nodes’ values.

For example:
Given binary tree {1,#,2,3},

return [1,2,3].

Note: Recursive solution is trivial, could you do it iteratively?

题目地址:leetcode Binary Tree Preorder Traversal

题意:给定二叉树,返回其前序遍历

思路:

  1. 直接递归。没难度。
  2. 用栈,记得应先右子树入栈。(why?递归的时候是先左子树的,而栈后进先出,故左子树要放后面入栈)

递归版

C++

 

Python

迭代版

C++

Python

 

 

 

145. Binary Tree Postorder Traversal

Given a binary tree, return the postorder traversal of its nodes’ values.

For example:
Given binary tree {1,#,2,3},

return [3,2,1].

Note: Recursive solution is trivial, could you do it iteratively?

题目地址:leetcode Binary Tree Postorder Traversal

题意:给定二叉树,返回其后序遍历

思路:递归就不说了。说说非递归版本。

我们做过,从前序和中序遍历构造出树,也做过从后序和中序遍历构造树的(见105和106题)

做完前序和中序的那时候我就想,前序和后序能否直接倒序得到?(想偷懒)

答案是否定的,我们来看看前序遍历:根-左子树-右子树

后序遍历:左子树-右子树-根 把前序遍历倒过来:右子树-左子树-根 !左右子树相反,不能直接倒!

但是这题,哼哼哼,先左子树入栈,在右子树入栈!(和前序遍历相反,也就是颠倒了左右子树),最后输出颠倒一下即可!

非递归版本

C++

Python

递归版本

 

 

 

173. Binary Search Tree Iterator

Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.

Calling next() will return the next smallest number in the BST.

Note: next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.

leetcode 173 Binary Search Tree Iterator

题目:写一个二叉搜索树(BST),要求实现hasnext和next函数。调用时会这么调用:while i.hasNext(): v.append(i.next())

思路:我们知道中序遍历结果就是有序的序列。只要用非递归的实现中序遍历即可。(见94题)

Python

 

 

 

199. Binary Tree Right Side View

Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

For example:
Given the following binary tree,

You should return [1, 3, 4].

题目地址:leetcode 199 Binary Tree Right Side View

题目:给定一颗二叉树,求每一层最右边的结点。

思路: 两种方法,我用的是DFS

  • BFS,直接求得每一层最右边的,很好理解,我就不想写了。
  • DFS:先求深度,然后dfs,每次将找到的放在相应的层上。由于右面放的一定是右边的结点,所以能保证正确。

 

 

 

222. Count Complete Tree Nodes

Given a complete binary tree, count the number of nodes.

Definition of a complete binary tree from Wikipedia:
In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2hnodes inclusive at the last level h.

题目地址:leetcode 222 Count Complete Tree Nodes

题意:给定一个完全二叉树(它的所有非叶子结点都有左和右子结点),求它的结点数

思路: 直接深搜O(n) TLE了。所以采用别的方法。

对于一个结点,计算其左子树和右子树的高度。如果相等,那么为满二叉树,结点数为2^h -1 否则递归计算

C

 

python

 

 

226. Invert Binary Tree

Invert a binary tree.

to

题目地址:leetcode 226 Invert Binary Tree

题意:给定一个二叉树,让你把它倒过来

思路:DFS的时候交换左右结点即可

 

 

230. Kth Smallest Element in a BST

Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.

Note:
You may assume k is always valid, 1 ≤ k ≤ BST’s total elements.

Follow up:
What if the BST is modified (insert/delete operations) often and you need to find the kth smallest frequently? How would you optimize the kthSmallest routine?

题目地址:leetcode 230 Kth Smallest Element in a BST

题意:给定BST,求BST中第k小的元素

思路: BST中序遍历为有序,所以直接中序遍历即可。