二叉树的各种算法面试题及答案解析，linux 基础教程第二版 pdf
import java.util.LinkedList;
public class Solution {
public int TreeDepth(TreeNode root) {
if(root==null){
return 0;
}
if(root.left==null&&root.right==null){
return 1;
}
int currentLevelNodes=1; //记录当前层的结点数量
int nextLevelNodes=0; //记录下一层结点的数量
int depth=0; //记录树的深度
Queue<TreeNode> queue=new LinkedList<TreeNode>();
queue.offer(root);
while(!queue.isEmpty()){
TreeNode node=queue.poll(); //取出一个结点，记录该结点的下一层结点，这也是 queue 的使用原因
currentLevelNodes--;
if(node.left!=null){
queue.offer(node.left);
nextLevelNodes++;
}
if(node.right!=null){
queue.offer(node.right);
nextLevelNodes++;
}
if(currentLevelNodes==0){
currentLevelNodes=nextLevelNodes;
nextLevelNodes=0;
depth++;
}
}
return depth;
}
}
[](
)树的深度计算（递归）
public class Solution {
public int TreeDepth(TreeNode root) {
if(root==null){
return 0;
}
if(root.left==null&&root.right==null){
return 1;
}
int leftLength=TreeDepth(root.left);
int rightLength=TreeDepth(root.right);
return Math.max(leftLength,rightLength)+1;
}
}
[](
)从上向下遍历树
记得使用队列 Queue！！
import java.util.Queue;
import java.util.LinkedList;
public class Solution {
public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
ArrayList<Integer> array=new ArrayList<Integer>();
if(root==null){
return array;
}
Queue<TreeNode> queue=new LinkedList<TreeNode>();
queue.offer(root);
while(!queue.isEmpty()){
TreeNode node=queue.poll();
if(node.left!=null){
queue.offer(node.left);
}
if(node.right!=null){
queue.
offer(node.right);
}
array.add(node.val);
}
return array;
}
}
[](
)前序遍历（递归）
这里的陷阱在于
ArrayList<Integer> array=new ArrayList<Integer>()；变量 array 的使用
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> preorderTraversal(TreeNode root) {
ArrayList<Integer> array=new ArrayList<Integer>();
if(root==null){
return array;
}
preorderTraversal(root,array);
return array;
}
public void preorderTraversal(TreeNode root,ArrayList<Integer> array){
if(root==null){
return;
}
array.add(root.val);
preorderTraversal(root.left,array);
preorderTraversal(root.right,array);
}
}
[](
)前序遍历（非递归）
使用栈，对于每一个结点来说，先将它的右节点放进去，再将左节点放进去，然后循环拿出栈顶元素，这样可以做到执行完所有的左子树才能轮上右子树。
import java.util.ArrayList;
import java.util.Stack;
public class Solution {
public ArrayList<Integer> preorderTraversal(TreeNode root) {
ArrayList<Integer> array=new ArrayList<Integer>();
if(root==null){
return array;
}
Stack<TreeNode> stack=new Stack<TreeNode>();
stack.push(root);
while(!stack.isEmpty()){
TreeNode node=stack.pop();
array.add(node.val);
if(node.right!=null){
stack.push(node.right);
}
if(node.left!=null){
stack.push(node.left);
}
}
return array;
}
}
[](
)中序遍历（递归）
这里的陷阱在于
ArrayList<Integer> array=new ArrayList<Integer>()；变量 array 的使用
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> inorderTraversal(TreeNode root) {
ArrayList<Integer> array=new ArrayList<Integer>();
if(root==null){
return array;
}
inorderTraversal(root,array);
return array;
}
public void inorderTraversal(TreeNode root,ArrayList<Integer> array){
if(root==null){
return;
}
inorderTraversal(root.left,array);
array.add(root.val);
inorderTraversal(root.right,array);
}
}
[](
)后序遍历（递归）
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> postorderTraversal(TreeNode root) {
ArrayList<Integer> array=new ArrayList<Integer>();
if(root==null){
return array;
}
postorderTraversal(root,array);
return array;
}
public void postorderTraversal(TreeNode root,ArrayList<Integer> array){
if(root==null){
return;
}
postorderTraversal(root.left,array);
postorderTraversal(root.right,array);
array.add(root.val);
}
}
[](
)二叉树中和为某一值的路径(递归)
public class Solution {
ArrayList<ArrayList<Integer>> array=new ArrayList<ArrayList<Integer>>();
ArrayList<Integer> temp=new ArrayList<Integer>();
public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
if(root==null){
return array;
}
temp.add(root.val);
target-=root.val;
if(target==0&&root.left==null&&root.right==null){
array.add(new ArrayList(temp)); //创建新的 ArrayList
}
FindPath(root.left,target);
FindPath(root.right,target);
temp.remove(temp.size()-1); //深度优先算法回退一步
return array;
}
}
还未添加个人签名 2021.03.18 加入
还未添加个人简介
评论