给网站开发APP,手赚网站哪里可以做,网站策划软件,苏州网站 建设 公司二叉树里的双指针
所谓的双指针就是定义了两个变量#xff0c;在二叉树中有需要至少定义两个变量才能解决问题。这两个指针可能针对一棵树#xff0c;也可能针对两棵树#xff0c;姑且也称之为“双指针”。这些问题一般与对称、反转和合并等类型题相关。
判断两棵树是否相…二叉树里的双指针
所谓的双指针就是定义了两个变量在二叉树中有需要至少定义两个变量才能解决问题。这两个指针可能针对一棵树也可能针对两棵树姑且也称之为“双指针”。这些问题一般与对称、反转和合并等类型题相关。
判断两棵树是否相同
100. 相同的树 - 力扣LeetCode
给你两棵二叉树的根节点 p 和 q 编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同并且节点具有相同的值则认为它们是相同的。
示例 1 输入p [1,2,3], q [1,2,3]
输出true示例 2 输入p [1,2], q [1,null,2]
输出false示例 3 输入p [1,2,1], q [1,1,2]
输出false提示
两棵树上的节点数目都在范围 [0, 100] 内-104 Node.val 104
同时进行前序遍历
两个二叉树同时进行前序遍历先判断根节点是否相同 如果相同再分别判断左右子树是否相同判断的过程中只要有一个不相同就返回 false全部相同才会返回true。
public boolean isSameTree(TreeNode p, TreeNode q)
{//如果结点都为null则认为两个结点相同if(p null q null)return true;//经过前面的判断到这里要么p、q都不为null,要么p、q中只有一个为null//若p、q一个为null一个不为null则认为两棵树不相同if(p null || q null)return false;//若结点值不同则认为两棵树不相同if(p.val ! q.val)return false;//该结点没问题接下来对该结点的左右子树进行对比分析return isSameTree(p.left, q.left) isSameTree(p.right, q.right);
}对称二叉树
101. 对称二叉树 - 力扣LeetCode
给你一个二叉树的根节点 root 检查它是否轴对称。
示例 1 输入root [1,2,2,3,4,4,3]
输出true示例 2 输入root [1,2,2,null,3,null,3]
输出false提示
树中节点数目在范围 [1, 1000] 内-100 Node.val 100
递归 若根结点的左右节点都不为 null 且 val 相同。
比较外侧是否对称传入的是左节点的左孩子右节点的右孩子。比较内侧是否对称传入的是左节点的右孩子右节点的左孩子。有一侧不对称就返回false 左右都对称则返回true 。
//主方法
public boolean isSymmetric(TreeNode root)
{return check(root.left, root.right);
}public boolean check(TreeNode p, TreeNode q)
{if (q null p null)return true;if(q null || p null)return false;if(q.val ! p.val)return false;return check(p.left ,q.right) check(p.right, q.left);
}合并二叉树
617. 合并二叉树 - 力扣LeetCode
给你两棵二叉树 root1 和 root2 。
想象一下当你将其中一棵覆盖到另一棵之上时两棵树上的一些节点将会重叠而另一些不会。你需要将这两棵树合并成一棵新二叉树。
合并的规则是如果两个节点重叠那么将这两个节点的值相加作为合并后节点的新值否则不为 null 的节点将直接作为新二叉树的节点。
返回合并后的二叉树。
注意: 合并过程必须从两个树的根节点开始。
示例 1 输入root1 [1,3,2,5], root2 [2,1,3,null,4,null,7]
输出[3,4,5,5,4,null,7]提示
两棵树中的节点数目在范围 [0, 2000] 内-104 Node.val 104
解
合并得到某个节点之后还要对该节点的左右子树分别进行合并
public TreeNode mergeTrees(TreeNode root1, TreeNode root2)
{//触底时返回 null 或者不为 null 的那个结点if (root1 null)return root2;if (root2 null)return root1;//两个结点均不为 null 则进行合并生成一个新结点显性合并TreeNode mergeNode new TreeNode(root1.val root2.val);//合并两个结点的左子树然后衔接到新结点上mergeNode.left mergeTrees(root1.left, root2.left);//合并两个结点的右子树然后衔接到新结点上mergeNode.right mergeTrees(root1.right, root2.right);return mergeNode; //返回合并后的新结点
}路径专题
二叉树的所有路径
257. 二叉树的所有路径 - 力扣LeetCode
给你一个二叉树的根节点 root 按 任意顺序 返回所有从根节点到叶子节点的路径。
叶子节点 是指没有子节点的节点。
示例 1 输入root [1,2,3,null,5]
输出[1-2-5,1-3]示例 2
输入root [1]
输出[1]提示
树中节点的数目在范围 [1, 100] 内
前序遍历 list
调整一下对结点的处理操作即可
public ListString binaryTreePaths(TreeNode root)
{ArrayListString list new ArrayList();preOrder(root, list, );return list;
}public void preOrder(TreeNode root, ListString list, String ans)
{if (root null)return;//找到一个叶子结点后将路径添加到列表返回if (root.left null root.right null){ans ans String.format(%s,root.val);list.add(ans);return;}//保存路径上的节点ans ans String.format(%s-,root.val);preOrder(root.left, list, ans);preOrder(root.right, list, ans);
}二叉树的路径总和
112. 路径总和 - 力扣LeetCode
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径这条路径上所有节点值相加等于目标和 targetSum 。如果存在返回 true 否则返回 false 。
叶子节点 是指没有子节点的节点。
示例 1 输入root [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum 22
输出true
解释等于目标和的根节点到叶节点路径如上图所示。示例 2
输入root [], targetSum 0
输出false
解释由于树是空的所以不存在根节点到叶子节点的路径。提示
树中节点的数目在范围 [0, 5000] 内
前序遍历 list
本来想着用一个 boolean 类型的 flag 标记一下即可但发现即使找到答案路径后flag 在往后的递归中也会受到影响而改变结果于是不得已用了一个列表来标记似乎列表才属于循环不变量、递归不变量
public boolean hasPathSum(TreeNode root, int targetSum)
{ArrayListBoolean list new ArrayListBoolean();preOrder(root,list,0, targetSum);return !list.isEmpty();
}public void preOrder(TreeNode root, ArrayListBoolean list, int sum, int targetSum)
{if (root null)return;//在叶子结点处进行判断然后返回if (root.left null root.right null){sum sum root.val;if(sum targetSum)list.add(true);return;}//计算路径上非叶节点的和sum sum root.val;preOrder(root.left, list, sum, targetSum );preOrder(root.right, list, sum, targetSum);
}递归地询问子节点是否满足条件
若当前节点就是叶子节点则直接判断 val 是否等于 targetSum若当前节点不是叶子节点则递归地询问它的两个子节点是否满足条件 val targetSum - 父节点.val 有一个满足即返回 true两个都不满足则返回 false 子节点为 null 视为不满足。
public boolean hasPathSum(TreeNode root, int targetSum)
{if (root null)return false;if (root.left null root.right null)return root.val targetSum;boolean left hasPathSum(root.left, targetSum - root.val);boolean right hasPathSum(root.right, targetSum - root.val);return left || right;
}翻转二叉树
226. 翻转二叉树 - 力扣LeetCode
给你一棵二叉树的根节点 root 翻转这棵二叉树并返回其根节点。
示例 1 输入root [4,2,7,1,3,6,9]
输出[4,7,2,9,6,3,1]递归
递归地翻转当前结点的两个子节点即可
public TreeNode invertTree(TreeNode root)
{if (root null)return null;TreeNode t root.left;root.left root.right;root.right t;invertTree(root.left);invertTree(root.right);return root;
}层次遍历
public TreeNode invertTree(TreeNode root)
{if (root null)return null;ArrayDequeTreeNode queue new ArrayDeque();queue.offer(root);while (!queue.isEmpty()){TreeNode curNode queue.poll();TreeNode t curNode.left;curNode.left curNode.right;curNode.right t;if (curNode.left ! null)queue.offer(curNode.left);if (curNode.right ! null)queue.offer(curNode.right);}return root;
}
