递归
采用深度优先遍历。
当root is None时，则return 0。
否则，返回左、右子树深度的最大值 + 1。
如果当前结点为空，则其高度为0。否则，就分别求其左、右子树的高度，然后取两个高度中的最大值 ，加1, 就是当前结点的高度。
class Solution:
def maxDepth(self, root: TreeNode) -> int:
return 0 if not root else max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1
|
class Solution {
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}
}
|
平衡二叉树：一个二叉树每个节点的左、右两个子树的高度差的绝对值不超过 1 。
空树也是平衡树（左、右子树的高度差为0）。
若不空，则计算当前节点左、右子树的高度差，如果高度差的绝对值不超过1，则平衡，否则不平衡。
class Solution:
def isBalanced(self, root: TreeNode) -> bool:
def height(root: TreeNode) -> int:
if not root:
return 0
return max(height(root.left), height(root.right)) + 1
if not root:
return True
return abs(height(root.left) - height(root.right)) <= 1 and self.isBalanced(root.left) and self.isBalanced(root.right)
|
下面提供另一种解法。
分别求左、右子树的高度，然后判断左、右子树的高度差。以及左、右子树的高度是否等于-1（-1的由来：如果当前结点的孩子节点的左、右子树的高度差大于1，那么就会返回-1）。
最后，判断根节点的高度是不是大于等于0。因为只要是树中有一个结点不是平衡树，则整棵树就不是平衡树。
class Solution {
int height(TreeNode root) {
if( root == null ) {
return 0;
}
int leftHeight = height(root.left);
int rightHeight = height(root.right);
if((Math.abs(leftHeight - rightHeight) > 1) || leftHeight == -1 || rightHeight == -1) {
return -1;
}
return Math.max(leftHeight, rightHeight) + 1;
}
public boolean isBalanced(TreeNode root) {
return height(root) >= 0;
}
}
|
题目中说「这条路径可能穿过也可能不穿过根结点」，所以对于每一棵子树的根节点，都可能是直径路径经过的结点。如图，根节点为2的这棵子树就是正确答案。
定义全局变量ans表示要求的直径长度所经过的结点个数。路径长度为两节点间经过的边的个数，也就等于结点数减1。所以最后求的直径长度为ans - 1。
下面我们分别求左、右子树的高度，然后+1，也就是所经过的结点个数。再和ans比较，取数值大者。
最后将ans - 1就是正确结果。
class Solution:
def diameterOfBinaryTree(self, root: TreeNode) -> int:
self.ans = 1
def height(root):
if not root:
return 0
leftHeight = height(root.left)
rightHeight = height(root.right)
self.ans = max(self.ans, leftHeight + rightHeight + 1)
return max(leftHeight, rightHeight) + 1
height(root)
return self.ans - 1
|
？？？？？？？？？？？？？？？？？
下面这个解法1是我挖的一个坑。↓。中计了。
在二叉树的遍历算法上做更改。
其实就是一个前序遍历，不过就是将打印结点值换成了交换结点值。
那中序遍历、后续遍历行不行呢？答案是，前序、后序遍历可以，中序遍历就不可以。那为什么中序不可以呢？
？？？？？？？？？？？？？？？？？
# 正解1
class Solution:
def invertTree(self, root: TreeNode) -> TreeNode:
if not root:
return None
t = root.left
root.left = root.right
root.right = t
self.invertTree(root.left)
self.invertTree(root.right)
return root
|
class Solution:
def invertTree(self, root: TreeNode) -> TreeNode:
if not root:
return
root.left, root.right = self.invertTree(root.right), self.invertTree(root.left)
return root
|
该题就是创建一个二叉树，不过创建的数据来自两棵二叉树。
我再贴一个创建二叉树的算法。
class Solution:
def mergeTrees(self, t1: TreeNode, t2: TreeNode) -> TreeNode:
if not t1:
return t2
if not t2:
return t1
merged = TreeNode(t1.val + t2.val)
merged.left = self.mergeTrees(t1.left, t2.left)
merged.right = self.mergeTrees(t1.right, t2.right)
return merged
|
def createBT(root: TreeNode) -> TreeNode:
data = input()
if d == `
return None
root = TreeNode(d)
root.left = createBT(root.left)
root.right = createBT(root.right)
return root
|
class Solution:
def hasPathSum(self, root: TreeNode, sum: int) -> bool:
if not root:
return False
if not root.left and not root.right:
return sum == root.val
return self.hasPathSum(root.left, sum - root.val) or self.hasPathSum(root.right, sum - root.val)
|
class Solution:
def hasPathSum(self, root: TreeNode, sum: int) -> bool:
if not root:
return False
que_node = collections.deque([root])
que_val = collections.deque([root.val])
while que_node:
now = que_node.popleft()
temp = que_val.popleft()
if not now.left and not now.right:
if temp == sum:
return True
continue
if now.left:
que_node.append(now.left)
que_val.append(now.left.val + temp)
if now.right:
que_node.append(now.right)
que_val.append(now.right.val + temp)
return False
|
用到了判断两棵树是否相等的算法。
class Solution:
def isSubtree(self, s: TreeNode, t: TreeNode) -> bool:
if not s and not t:
return True
if not s or not t:
return False
return self.isSameTree(s, t) or self.isSubtree(s.left, t) or self.isSubtree(s.right, t)
def isSameTree(self, s, t):
if not s and not t:
return True
if not s or not t:
return False
return s.val == t.val and self.isSameTree(s.left, t.left) and self.isSameTree(s.right, t.right)
|
