城志

分类

题解(21)

/ 注册

全部文章（共8篇）

判断二叉树是否对称

递归 1. 分析不对称的条件：结点X的左右子树不对称，包括左右子树某一个为null，左右孩子的val不同，左孩子的左子树与右孩子的右子树不对称等等递归的base case是假设知道左右两个子树是否为null、根以及左右子树是否对称。 2. 代码 public class Solution { ...

剑指offer java 二叉树

2020-02-23

0 906

二叉树的最大二叉搜索子树

【典型】树的动态规划问题 1. 分析树形动态规划问题的前提：如果题目要求的目标是规则S，则流程一般是完成每个结点为root时的子树，在规则S下的每一个答案，最终答案一定在这些答案中。本题中，规则是整棵树的最大搜索二叉树（maxBST）。求出每一个节点作为root的子树的maxBST，最终答案...

左程云 java 二叉树 leetcode

2020-02-22

0 1666

验证平衡二叉树

树形动态规划 1.套路 1.1 可能性分析如果root的左子树不是平衡二叉树，则root不是。如果root的右子树不是，则root不是。如果root的左右子树的高度差超过1，则root不是。如果以上三种没出现，那么root是平衡的。 1.2 建立数据结构根据可能性分析列出每个结点所需信...

java 二叉树 leetcode

2020-02-22

0 1153

二叉树某结点在中序遍历的下一个结点

1. 分情况列举 1.1 分析有右孩，返回右子树的中序最左结点无右孩,且它是父亲的左孩，则返回其父无右孩，且它是其父亲的右孩，则从它父亲开始往上找, 直到某个结点，它是其父亲的左孩，返回其父亲。 1.2 代码 /* public class TreeLinkNode { int v...

剑指offer java 二叉树

2020-02-21

0 959

根据先序和中序遍历重建二叉树

1. 递归 1.1 分析 pre[0]是root,在in中找到root的位置找到root位置后，根据其index确定左右子树的pre和in的范围, 递归图片转载自 https://blog.nowcoder.net/n/7131c90ce3214472887b0f2f6652f5a7 注意，Ar...

剑指offer java 二叉树

2020-02-21

0 942

按之字形打印二叉树

1. 双端队列+层次遍历 1.1 分析之字形，要求奇偶层输出顺序相反。双端队列基于LinkedList实现。奇数层，队头出对，孩子从队尾入队，先左后右。偶数层，队尾出队，孩子从队头入队，先右后左。 1.2 代码 import java.util.ArrayList; import java....

左程云 java 二叉树

2020-02-20

0 932

二叉树层次遍历，按层输出

1. 标记每层最右结点 1.1 分析辅助队列last记录本层最右结点，nLast记录下层最右结点（入队时标记）。出队到last时本层输出完，last更新为nLast。 1.2 代码 import java.util.* public class Solution { ArrayList&l...

左程云 java 二叉树

2020-02-20

0 1493

非递归遍历二叉树

import java.util.Stack; class Node{ Node left; Node right; char val; public void Node(char value){ this.val = value; } } ...

左程云 java 二叉树

2020-02-20

0 1055