算法 求二叉树根节点到指定节点的路径
@author:Jingdai
@date:2020.11.05
题目描述
给你一个棵二叉树，再给你一个指定的节点，求根节点到指定节点的路径。
如图，比如让你求到 4 节点的路径，则应该返回的路径为
[0, 1, 4]。
思路
利用二叉树的先序遍历，寻找指定的节点，同时用一个栈 stack 记录遍历到的节点，当找到需要的节点后立即返回结果。但是这样有一个问题，就是在遍历中 stack 记录的路径中包含一些其他的节点，比如要求上图中到 4 节点的路径，则遍历到 4 节点时，stack 中的路径就为 [0, 1, 3, 5, 6, 7, 8, 4]，而需要的路径为 [0, 1, 4] ，中间多了许多不需要的节点。
为了去掉 stack 中不需要的节点，需要在递归查找过程中进行回溯，pop 这些不需要的节点。先序遍历查找是先看根节点是否满足要求、若不满足要求再去左子树和右子树中去查找，如果右子树还是找不到，说明该节点不在路径中，需要弹出该节点。
综上，代码片段如下：
public static boolean getPathToTarget(TreeNode node, TreeNode target, LinkedList<TreeNode> path) {if (node == null) return false;path.push(node);if (node == target)return true;// find in left treeif (getPathToTarget(node.left, target, path)) return true; // find in right treeif (getPathToTarget(node.right, target, path))return true;// this node is not in the path of target// cause leftchild rightchild and itself do not have target nodepath.pop();return false;
}
为了测试整个代码的正确性，使用LeetCode 定义的 TreeNode 来建立树，然后进行测试，完整的代码如下。
代码
import java.util.*;public class Solution {public static void main(String[] args) {// create treeTreeNode root = new TreeNode(0);TreeNode node1 = new TreeNode(1);TreeNode node2 = new TreeNode(2);TreeNode node3 = new TreeNode(3);TreeNode node4 = new TreeNode(4);TreeNode node5 = new TreeNode(5);TreeNode node6 = new TreeNode(6);TreeNode node7 = new TreeNode(7);TreeNode node8 = new TreeNode(8);root.left = node1;root.right = node2;node1.left = node3;node1.right = node4;node3.left = node5;node3.right = node6;node6.left = node7;node6.right = node8;// testLinkedList<TreeNode> path = new LinkedList<>();// get the path to node4boolean hasPath = getPathToTarget(root, node4, path);if (hasPath) {for (TreeNode node : path) {System.out.print(node.val + " ");}}System.out.println();System.out.println("============");path.clear();// get the path to nonexistent nodehasPath = getPathToTarget(root, new TreeNode(9), path);if (hasPath) {for (TreeNode node : path) {System.out.print(node.val + " ");}}}public static boolean getPathToTarget(TreeNode node, TreeNode target, LinkedList<TreeNode> path) {if (node == null) return false;path.push(node);if (node == target)return true;// find in left treeif (getPathToTarget(node.left, target, path)) return true; // find in right treeif (getPathToTarget(node.right, target, path))return true;// this node is not in the path of target// cause leftchild rightchild and itself do not have target nodepath.pop();return false;}
}class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int x) { val = x; }
}
